Number of Good Pairs
Problem Description
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:
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5).
Example 2:
Explanation: Each pair in the array are good.
Example 3:
Constraints:
- 1 <= nums.length <= 100
- 1 <= nums[i] <= 100
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The simplest approach is to check every possible pair (i, j) where 0 <= i < j < nums.length and check if they are equal. If they are, we have found a "good pair."
Steps:
- Initialize a counter
countto zero to keep track of good pairs. - Use two nested loops, the outer loop (
i) goes from0tonums.length - 1, and the inner loop (j) runs fromi+1tonums.length - 1. - For each pair
(i, j), check ifnums[i] == nums[j]. If yes, increment thecount. - Return the
countafter both loops have finished.
Code:
- Time Complexity: O(n^2) due to nested for loops.
- Space Complexity: O(1).
2. HashMap
Intuition:
Instead of comparing pairs directly (which would take O(n²) time), we can count how many times each number appears using a HashMap. Every time we encounter a number we've already seen, it forms a “good pair” with all its previous occurrences.
If a number appears n times, the total number of good pairs formed by that number is:
But rather than using the formula at the end, we can compute pairs incrementally as we traverse the array:
- When the first occurrence arrives → contributes 0 pairs
- Second occurrence → contributes 1 new pair
- Third occurrence → contributes 2 new pairs
- Fourth occurrence → contributes 3 new pairs
- … and so on
So when we encounter a number again, we simply add its current frequency to the answer.
Steps:
- Use a HashMap to store the frequency of each number in the array.
- Iterate through the array, updating the frequency of each number in the HashMap.
- For each number encountered again, increment the count of good pairs using the formula for combinations since each new occurrence can pair with all previous ones.
- Return the total count of good pairs.
Code:
- Time Complexity: O(n) since iterating through the array only once.
- Space Complexity: O(n) since using hashmap. In the worse case, it may end up storing all the array elements.