Start by mapping each number in the array to its occurrence count using a hash map. Then for each number, compute the number of good pairs as count * (count - 1) // 2 and sum these totals. This approach ensures O(n) traversal and avoids redundant comparisons while directly leveraging the array scanning plus hash lookup pattern.
Problem Statement
Given an integer array nums, determine the total number of good pairs present. A pair (i, j) is good if nums[i] equals nums[j] and i is less than j.
Return the count of all such good pairs. For example, given nums = [1,2,3,1,1,3], the pairs (0,3), (0,4), (3,4), and (2,5) are good, totaling 4 good pairs.
Examples
Example 1
Input: nums = [1,2,3,1,1,3]
Output: 4
There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.
Example 2
Input: nums = [1,1,1,1]
Output: 6
Each pair in the array are good.
Example 3
Input: nums = [1,2,3]
Output: 0
Example details omitted.
Constraints
- 1 <= nums.length <= 100
- 1 <= nums[i] <= 100
Solution Approach
Hash Map Counting
Traverse the array once and store each number's frequency in a hash map. Then for each unique number, calculate pairs with the formula count * (count - 1) // 2 and sum them.
Single-Pass Incremental Counting
Iterate through the array while maintaining a running hash of seen numbers. For each element, add its current count in the hash to a total good pair counter and then increment its count in the hash map.
Mathematical Combination Optimization
Instead of explicitly generating pairs, use the combination formula nC2 for each number's frequency. This leverages the observation that n occurrences produce n * (n - 1) // 2 good pairs directly.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n) due to a single pass through the array and hash operations. Space complexity is O(k) where k is the number of unique elements in nums, bounded by 100 per constraints.
What Interviewers Usually Probe
- Do you recognize a counting or frequency pattern here?
- Consider using a hash map to avoid nested loops.
- Ask yourself if you can calculate pairs without generating them explicitly.
Common Pitfalls or Variants
Common pitfalls
- Double-counting pairs by iterating over all i < j combinations.
- Forgetting that i must be less than j, not just matching values.
- Using nested loops unnecessarily instead of leveraging hash counts.
Follow-up variants
- Count good pairs where i > j instead of i < j, adjusting logic accordingly.
- Determine number of good triplets (i < j < k) with equal values using extended frequency counting.
- Compute good pairs under a modulo constraint on the values to test handling of hash keys.
How GhostInterview Helps
- Highlights the array scanning plus hash lookup pattern immediately.
- Provides formula-based pair counting to prevent redundant iteration errors.
- Identifies failure modes like double-counting and inefficient nested loops automatically.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What defines a good pair in Number of Good Pairs?
A good pair is a pair of indices (i, j) where nums[i] equals nums[j] and i is less than j.
How does the array scanning plus hash lookup pattern apply?
It allows counting occurrences in a single pass and calculating good pairs efficiently using the frequency map.
Can this approach handle the maximum array size efficiently?
Yes, with 1 <= nums.length <= 100, a hash map approach achieves O(n) time and O(k) space without performance issues.
Is there a formula to count pairs without nested loops?
Yes, for a number appearing n times, the number of good pairs is n * (n - 1) // 2.
What mistakes should I avoid for Number of Good Pairs?
Avoid double-counting, ensure i < j, and don't use unnecessary nested loops when hash counting suffices.
Need direct help with Number of Good Pairs instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Number of Good Pairs from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Count Nice Pairs in an Array requires efficiently pairing numbers where nums[i] + rev(nums[j]) equals nums[j] + rev(nums[i]).
Open problem page#1994 The Number of Good SubsetsFind the number of good subsets in an integer array, where each subset's product is the product of distinct primes.
Open problem page#2001 Number of Pairs of Interchangeable RectanglesCount all pairs of rectangles that share the exact width-to-height ratio using efficient array scanning and hash lookup.
Open problem page