Number of Good Pairs
Problem
Return the number of good pairs (i,j) with i < j and nums[i] == nums[j].
nums = [1,2,3,1,1,3]4from collections import Counter
def num_identical_pairs(nums):
return sum(c * (c - 1) // 2 for c in Counter(nums).values())function numIdenticalPairs(nums) {
const f = {}; for (const x of nums) f[x] = (f[x] || 0) + 1;
let ans = 0; for (const c of Object.values(f)) ans += c * (c - 1) / 2;
return ans;
}class Solution {
public int numIdenticalPairs(int[] nums) {
Map f = new HashMap<>();
for (int x : nums) f.merge(x, 1, Integer::sum);
int ans = 0;
for (int c : f.values()) ans += c * (c - 1) / 2;
return ans;
}
} int numIdenticalPairs(vector& nums) {
unordered_map f;
for (int x : nums) f[x]++;
int ans = 0;
for (auto& p : f) ans += p.second * (p.second - 1) / 2;
return ans;
} Explanation
A good pair is two equal numbers at different positions. Instead of checking every pair, we notice that the answer only depends on how many times each value appears.
If a value shows up c times, the number of ways to pick two of those positions is the combination C(c, 2) = c·(c-1)/2. So we count frequencies with a map (Python's Counter) and add up that formula over every value.
This turns an O(n²) pair scan into a quick frequency tally plus a little arithmetic.
Example: nums = [1,2,3,1,1,3]. Value 1 appears 3 times → 3·2/2 = 3; value 3 appears twice → 2·1/2 = 1; everything else once → 0. Total = 4.
Because each value's contribution is computed directly from its count, one pass to build frequencies is all we need.