Approach Summary
Track frequency of each number. When we see nums[i] for the k-th time it forms k-1 new good pairs. Sum those counts.
How to Recognize This Pattern
- Count pairs (i,j) where i < j and nums[i] == nums[j]
- Each new occurrence pairs with all prior occurrences
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
Tags
Array Hash Table Math Counting