Given an array of integers nums, return the number of good pairs.
A pair (i, j) is called good if nums[i] == nums[j] and i < j.
Example 1:
Input: nums = [1,2,3,1,1,3] Output: 4 Explanation: 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 Explanation: Each pair in the array are good.
Example 3:
Input: nums = [1,2,3] Output: 0
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 100Problem Overview: Given an integer array nums, count the number of pairs (i, j) such that nums[i] == nums[j] and i < j. A pair is considered "good" when both indices point to the same value and the first index appears before the second.
Approach 1: Brute Force Pair Comparison (O(n²) time, O(1) space)
The most direct solution checks every possible pair of indices. Use two nested loops: the outer loop selects index i, and the inner loop scans indices j from i + 1 to the end of the array. Each time nums[i] == nums[j], increment the counter. This method performs roughly n * (n-1) / 2 comparisons, which leads to O(n²) time complexity and constant O(1) extra space.
This approach works well for small arrays and helps demonstrate a clear understanding of the problem definition. However, performance degrades quickly as the array grows because every pair is explicitly checked. Problems involving pair counting in an array often require a more efficient counting strategy.
Approach 2: Hash Map Frequency Counting (O(n) time, O(n) space)
A faster solution counts how many times each number has already appeared while iterating through the array. Maintain a hash map where the key is the number and the value is its frequency so far. When processing a new element x, the number of new good pairs formed equals the current frequency of x. Add that frequency to the result, then increment the stored count.
Example: if the value 3 has already appeared 4 times, the next 3 forms 4 new good pairs. This works because each previous occurrence creates one valid pair with the current index. Each iteration performs a constant-time hash lookup and update, producing O(n) time complexity and O(n) space complexity.
This technique relies on frequency tracking, a common pattern in hash table problems and counting problems. Mathematically, the process mirrors the combination formula for choosing two identical values from a group, which connects to counting techniques.
Recommended for interviews: Interviewers typically expect the hash map frequency approach. The brute force method shows you understand the definition of a good pair and can reason about pair enumeration. The optimized solution demonstrates familiarity with hash-based counting patterns and reduces the runtime from quadratic O(n²) to linear O(n), which is the standard expectation for this problem.
This approach involves using two nested loops to check all possible pairs of indices in the array. For each pair, we check if it satisfies the condition for being a good pair and count it if it does.
This C solution uses two for loops to iterate through all pairs of indices. We start with index i and compare it with all subsequent indices j. If a good pair is found, we increment the count variable.
Time Complexity: O(n^2), where n is the length of the array. We are checking all possible pairs.
Space Complexity: O(1), as we are not using any additional data structures.
This approach optimizes the search for good pairs using a hash map (or dictionary). Instead of checking each pair directly, we track the number of occurrences of each number as we iterate through the array. For each new element, the number of good pairs it can form is equal to the frequency of the element seen so far.
This C solution uses an array as a frequency counter. As each number is processed, its count in the array gets added to the good pair count, then incremented to indicate its increased frequency.
Time Complexity: O(n), since each element is processed once.
Space Complexity: O(1), considering the fixed size of the frequency array which is independent of input size.
Traverse the array, and for each element x, count how many elements before it are equal to x. This count represents the number of good pairs formed by x and the previous elements. After traversing the entire array, we obtain the answer.
The time complexity is O(n), and the space complexity is O(C). Here, n is the length of the array, and C is the range of values in the array. In this problem, C = 101.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
PHP
C
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2), where n is the length of the array. We are checking all possible pairs. |
| Optimized Approach Using Hash Map | Time Complexity: O(n), since each element is processed once. |
| Counting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Comparison | O(n²) | O(1) | Small input sizes or when demonstrating the basic logic of pair enumeration |
| Hash Map Frequency Counting | O(n) | O(n) | General case and interview settings where linear time is expected |
Number of Good Pairs (LeetCode 1512) | Full solution with visuals and examples | Study Algorithms • Nikhil Lohia • 25,558 views views
Watch 9 more video solutions →Practice Number of Good Pairs with our built-in code editor and test cases.
Practice on FleetCode