Number of Good Pairs
Count pairs of equal elements by counting occurrences instead of comparing every pair
Problem Statement
Given an array nums, a pair (i, j) is good if nums[i] == nums[j] and i < j. Return the number of good pairs.
Input: nums = [1, 2, 3, 1, 1, 3]
Output: 4
Why: (0,3), (0,4), (3,4) for value 1, and (2,5) for value 3
Input: nums = [1, 1, 1, 1]
Output: 6
Input: nums = [1, 2, 3]
Output: 0Intuition
The brute force is exactly the definition: two nested loops over i < j, counting matches. That is O(n²).
The faster route starts with a re-framing. Pairs never form between different values — only identical ones. So the array splits into independent groups, one per distinct value, and the answer is the sum over groups.
The key insight
If a value appears c times, how many pairs does it contribute? Choose 2 of the c positions:
c × (c - 1) / 2
So you never need the positions at all — just the counts.
Check it against the example: 1 appears 3 times → 3 × 2 / 2 = 3 pairs. 3 appears twice → 2 × 1 / 2 = 1 pair. 2 appears once → 0. Total 4. ✓
Why c × (c - 1) / 2
Each of the c copies can pair with the other c - 1, giving c × (c - 1) ordered pairs. But (i, j) and (j, i) are the same pair counted twice, so halve it. For c = 4: 4 × 3 / 2 = 6, matching the second example.
The even slicker version
There is a way to avoid the formula entirely. Walk left to right and, at each element, ask: how many copies of this value have I already passed? Every one of them forms a good pair with the current position, because their index is smaller.
empty
Approach
Keep a count map
value → how many times it has appeared so far.
For each element, add the current count to the answer
Every earlier copy pairs with this position, and all of them satisfy i < j automatically.
Solution
from collections import defaultdict
def num_identical_pairs(nums: list[int]) -> int:
"""Count pairs (i, j) with i < j and nums[i] == nums[j]."""
seen: defaultdict[int, int] = defaultdict(int)
total = 0
for num in nums:
total += seen[num] # every earlier copy pairs with this one
seen[num] += 1
return totalThe formula version, if you prefer counting first:
from collections import Counter
def num_identical_pairs_formula(nums: list[int]) -> int:
return sum(c * (c - 1) // 2 for c in Counter(nums).values())Integer division in Python
Use // for c * (c - 1) // 2. A single / produces a float, and the expected answer is an integer. In TypeScript c * (c - 1) is always even, so / 2 gives an exact whole number.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(k)
- Time — one pass with
O(1)map operations, versusO(n²)for nested loops. Atn = 10⁵that is 100,000 steps instead of ~5 billion. - Space —
O(k)wherekis the number of distinct values, at worstO(n).
A constant-space variant
The LeetCode constraints cap values at 1 ≤ nums[i] ≤ 100. That lets you swap the hash map for a fixed array of 101 counters, giving genuinely O(1) space. Reading the constraints often reveals shortcuts like this.
Edge Cases
Related Problems
- Contains Duplicate — presence rather than counts
- Valid Anagram — comparing two count maps
- Top K Frequent Elements — ranking by count