Number of Good Pairs
Problem
Given an integer array nums, return the number of good pairs where a pair (i, j) is good if nums[i] == nums[j] and i < j.
- 1 ≤ nums.length ≤ 100
- 1 ≤ nums[i] ≤ 100
Example
nums = [1,2,3,1,1,3]4The brute-force approach would check every pair (i, j) with i < j, counting those where nums[i] == nums[j]. This is O(n²) and inefficient for large inputs. The optimal approach uses a frequency map to count how many times each number has appeared so far. For each new occurrence of a number, the number of good pairs increases by the count of previous occurrences of that number. For example, when processing the first '1', no pairs are formed. The second '1' forms one pair with the first. The third '1' forms two pairs with the previous two '1's, adding to the total count. This incremental counting avoids nested loops and achieves O(n) time.
Approach
Straightforward Solution
A brute-force nested loop checks all pairs (i, j) with i < j, comparing nums[i] and nums[j]. This approach is O(n²) and inefficient for larger arrays.
Core Observation
Each good pair corresponds to two identical numbers at different indices with the first index less than the second. Counting pairs directly is equivalent to counting combinations of identical elements.
Path to Optimal
The key insight is that for each number, the number of new good pairs formed when encountering it again equals the count of how many times it has appeared before. By maintaining a frequency map, the algorithm can incrementally add these counts in a single pass, reducing time complexity to O(n).
Optimal Approach
Iterate through nums once, maintaining a hash map of frequencies. For each number, add the current frequency count to the answer before incrementing the count. This counts all pairs formed by the current number with its previous occurrences, achieving O(n) time and O(n) space.
Time
O(n)
The algorithm iterates through the array once, performing O(1) average-time hash map operations per element.
Space
O(n)
The hash map stores counts for each unique number, which in the worst case can be all n elements.
Pattern Spotlight
Hash Maps (Frequency Counting)
When counting pairs or combinations of identical elements, track frequencies incrementally and add the current frequency to the result before updating it, enabling O(n) counting of pairs without nested loops.
Solution
| 1 | from collections import defaultdict |
| 2 | |
| 3 | class Solution: |
| 4 | def numIdenticalPairs(self, nums: List[int]) -> int: |
| 5 | freq = defaultdict(int) |
| 6 | ans = 0 |
| 7 | |
| 8 | for n in nums: |
| 9 | ans += freq[n] |
| 10 | freq[n] += 1 |
| 11 | |
| 12 | return ans |
Step-by-Step Solution
Accumulate Good Pairs by Tracking Frequencies in One Pass
| 5 | freq = defaultdict(int) |
| 6 | ans = 0 |
| 8 | for n in nums: |
| 9 | ans += freq[n] |
| 10 | freq[n] += 1 |
| 12 | return ans |
Objective
To count the number of good pairs by incrementally adding the frequency of each number before updating it.
Key Insight
Each time a number is encountered, the number of new good pairs formed equals how many times it has appeared before. By adding the current frequency to the answer before incrementing, the algorithm counts all pairs involving the current element and its previous occurrences without double counting or nested loops.
Interview Quick-Check
Core Logic
Add the current frequency of the number to the answer before incrementing the frequency to count all pairs formed by the current occurrence.
State & Boundaries
Initialize frequencies to zero and increment after counting pairs to maintain correct pair ordering (i < j).
Common Pitfalls & Bugs
Adding the frequency after incrementing would overcount pairs or count pairs with the same index.
Complexity
This approach achieves O(n) time and O(n) space, optimal for this problem.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
ans += freq[n]Add the current frequency of the number to the answer.
This line counts all new good pairs formed by the current occurrence with all previous occurrences of the same number, ensuring pairs are counted exactly once and respecting the order i < j.
freq[n] += 1Increment the frequency count for the current number.
Updating the frequency after counting pairs ensures that future occurrences will correctly count pairs with this occurrence.
freq = defaultdict(int)Initialize a default dictionary to count frequencies of numbers.
Using a defaultdict(int) allows automatic zero initialization for unseen keys, simplifying frequency tracking and enabling O(1) average-time updates.
return ansReturn the total count of good pairs.
Returning the accumulated answer completes the function, providing the final count of all good pairs found.
for n in nums:Iterate through each number in the input array.
A single pass over the array is sufficient to count all good pairs incrementally, enabling O(n) time complexity.
ans = 0Initialize the answer accumulator to zero.
This variable accumulates the total count of good pairs as the algorithm processes the array.
Test Your Understanding
Why does adding the current frequency count to the answer before incrementing correctly count all good pairs?
Because the current frequency represents how many previous occurrences of the number exist, each of which forms a good pair with the current element. Adding before incrementing ensures pairs are counted only once and respects the i < j condition.
Related Problems
Hash Maps pattern
Don't just read it. Drill it.
Reconstruct Number of Good Pairs from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Number of Good Pairs drill