Number of Good Pairs
Easy Counting
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Count pairs of indexes (i, j) with i < j where nums[i] equals nums[j].
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: count pairs of equal values (i before j).
Why this works: when a value appears for the k-th time, it makes a new pair with each of the k-1 earlier copies. Keep a count per value and add it before increasing.
Example: nums = [1, 2, 3, 1, 1, 3]
1: seen 0 before → +0 (seen[1]=1)2: +0, 3: +01: seen 1 before → +1 (seen[1]=2)1: seen 2 before → +2 (seen[1]=3)3: seen 1 before → +1total = 4
✦Hints open one at a time
↗Approach
Keep a count of each value seen so far. Before increasing the count of the current value, add that count to the answer. One pass, O(n) — the same answer as the O(n²) double loop, which is the whole point of complexity analysis.
</>Solution (Java)
class Solution {
public int numIdenticalPairs(int[] nums) {
int[] seen = new int[101];
int pairs = 0;
for (int x : nums) {
pairs += seen[x]; // pair with every earlier copy
seen[x]++;
}
return pairs;
}
}!Common mistake
Incrementing the count before adding it, which counts each element as a pair with itself.
- Time: O(n).
- Space: O(R) for the counts (values are at most 100).
