#1512 Number of Good Pairs
the problem
In plain words
A pair of indexes (i, j) is good when i < j and nums[i] == nums[j]. Return how many good pairs the array has.
in nums = [1,2,3,1,1,3]
out 4
(0,3), (0,4), (3,4), (2,5).
in nums = [1,1,1,1]
out 6
Every pair is good: 4·3/2.
in nums = [1,2,3]
out 0
- 1 ≤ nums.length ≤ 100
- 1 ≤ nums[i] ≤ 100
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternFrequency countingMath shortcut (closed form)
When a value x arrives, it forms a good pair with every earlier copy of x. Keep a count per value and add it before incrementing.
solutions
From brute force to optimal
Check all pairs i < j.
- Two loops, j starting at i + 1.
- Count the pairs with equal values.
n(n − 1)/2 pairs.
One counter.
class Solution { public int numIdenticalPairs(int[] nums) { int pairs = 0; for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { // j > i: each pair once if (nums[i] == nums[j]) pairs++; } } return pairs; }}seen[x] = copies of x so far; a new x adds that many pairs.
- seen = new int[101].
- For each x: pairs += seen[x], then seen[x]++.
One pass with O(1) array work per element.
101 counters, fixed by the value range.
class Solution { public int numIdenticalPairs(int[] nums) { int[] seen = new int[101]; // values are 1..100, so the value IS the index int pairs = 0; for (int x : nums) { pairs += seen[x]; // x pairs with every earlier copy of x seen[x]++; } return pairs; }}c copies of a value make c·(c−1)/2 pairs.
- Count every value.
- Sum c·(c−1)/2 over the counts.
One pass to count, 101 steps to sum.
101 counters.
class Solution { public int numIdenticalPairs(int[] nums) { int[] count = new int[101]; for (int x : nums) count[x]++; int pairs = 0; for (int c : count) pairs += c * (c - 1) / 2; // c copies make c·(c−1)/2 pairs return pairs; }}in the room
How to say it in the interview
talk track
- Brute force is fine for n ≤ 100 — say so, then give the O(n) counting version anyway.
- Explain why you add before incrementing: otherwise x pairs with itself.
traps
- Incrementing before adding counts each element as a pair with itself.
- With big counts,
c * (c - 1)overflowsintonce c passes about 46,000 — compute it inlong.
what they ask next
Follow-ups
Values up to 10⁹ instead of 100?
Swap int[101] for a HashMap<Integer, Integer> with merge(x, 1, Integer::sum) — still O(n) on average.
before you submit
Edge cases to test
- All equal: n·(n−1)/2 (100 equal values → 4,950).
- All distinct → 0.
- A single element → 0.
practise next
Similar problems
- #1Two SumEasyin Hashing
- #560Subarray Sum Equals KMediumin Hashing
- #217Contains DuplicateEasyin Hashing