Number of Good Pairs
EasyPrompt
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] <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses two nested loops to iterate through all possible pairs of indices (i, j) in the array. It checks if the elements at these indices are equal and if i < j. If both conditions are met, a counter is incremented.
Algorithm
- Initialize a counter
goodPairsCountto 0. - Get the length of the array,
n. - Loop with an index
ifrom0ton-2. - Inside this loop, start another loop with an index
jfromi+1ton-1. - Check if
nums[i]is equal tonums[j]. - If they are equal, increment
goodPairsCount. - After the loops complete, return
goodPairsCount.
Walkthrough
The simplest way to solve the problem is to check every possible pair of indices (i, j) and see if they form a good pair. We can use a nested loop structure. The outer loop iterates from i = 0 to n-1, and the inner loop iterates from j = i + 1 to n-1. This structure naturally ensures that i < j. Inside the inner loop, we compare nums[i] and nums[j]. If they are equal, we've found a good pair and we increment our total count. After checking all pairs, the final count is the answer.
class Solution { public int numIdenticalPairs(int[] nums) { int goodPairsCount = 0; int n = nums.length; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (nums[i] == nums[j]) { goodPairsCount++; } } } return goodPairsCount; }}Complexity
Time
O(n^2), where n is the number of elements in the `nums` array. This is because for each element, we iterate through the rest of the array, leading to a quadratic number of comparisons.
Space
O(1), as we only use a constant amount of extra space for the counter and loop variables.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra memory, making it space-efficient.
Cons
Inefficient for large arrays due to its quadratic time complexity.
A more efficient approach involves counting the frequency of each number in the array first. If a number appears k times, it can form k * (k - 1) / 2 pairs. We can sum these values for all numbers to get the total count of good pairs.
Algorithm
- Create a frequency array
countsof size 101 (based on constraints) and initialize it to zeros. - Iterate through the
numsarray and populate the frequency array. For eachnum, incrementcounts[num]. - Initialize a counter
goodPairsCountto 0. - Iterate through the
countsarray. - For each frequency
k, calculate the number of pairs it can form using the formula(k * (k - 1)) / 2and add it togoodPairsCount. - Return
goodPairsCount.
Walkthrough
This method optimizes the counting process by first aggregating the data. Instead of comparing each pair, we count how many times each number appears in the array. We can use a Hash Map or, given the constraints 1 <= nums[i] <= 100, a simple array of size 101 to store the frequency of each number. We iterate through the input array once to build this frequency map. After counting, we iterate through the frequencies. For any number that appears k times (where k > 1), the number of good pairs it can form is given by the combination formula 'k choose 2', which is k * (k - 1) / 2. By summing up these pair counts for every number, we get the total number of good pairs in the entire array.
class Solution { public int numIdenticalPairs(int[] nums) { int[] counts = new int[101]; for (int num : nums) { counts[num]++; } int goodPairsCount = 0; for (int count : counts) { if (count > 1) { goodPairsCount += (count * (count - 1)) / 2; } } return goodPairsCount; }}Complexity
Time
O(n), where n is the number of elements. We perform one pass to build the frequency map and another pass over the unique elements (at most 101 in this case). This is a significant improvement over the brute-force approach.
Space
O(1), given the problem constraints (`1 <= nums[i] <= 100`), we can use a fixed-size array of 101. If the constraints were not fixed, it would be O(k) where k is the number of unique elements.
Trade-offs
Pros
Significantly faster with O(n) time complexity.
The logic is based on a common combinatorial pattern.
Cons
Requires extra space to store the frequencies.
This is the most efficient approach. It combines counting frequencies and calculating pairs into a single pass through the array. As we iterate, we use a frequency array to keep track of the counts of numbers seen so far. For each number, we add its current count to our total before incrementing its count in the map.
Algorithm
- Initialize
goodPairsCountto 0. - Initialize a frequency array
countsof size 101 with all zeros. - Iterate through each
numin thenumsarray. - For the current
num, the number of pairs it can form with previous identical numbers iscounts[num]. Add this value togoodPairsCount. - Increment the count for the current number:
counts[num]++. - After the loop, return
goodPairsCount.
Walkthrough
This approach refines the frequency counting method by calculating the good pairs on the fly in a single pass. We initialize a counter for good pairs and a frequency array. We iterate through the nums array. For each element num, we first look up its current frequency in our array. Let's say we have seen num k times already. This means the current num can form k new good pairs with the ones we've already encountered. So, we add k to our total goodPairsCount. Then, we update the array by incrementing the frequency of num by 1 to account for the current element. This way, we build the counts and sum the pairs simultaneously.
class Solution { public int numIdenticalPairs(int[] nums) { int goodPairsCount = 0; int[] counts = new int[101]; // Constraints: 1 <= nums[i] <= 100 for (int num : nums) { // The current number `num` can form a pair with all previous occurrences. // The number of previous occurrences is `counts[num]`. goodPairsCount += counts[num]; // Increment the count for the current number for subsequent elements. counts[num]++; } return goodPairsCount; }}Complexity
Time
O(n), as we iterate through the array only once.
Space
O(1), due to the problem's constraints on the values in `nums`, allowing a fixed-size array. Without these constraints, it would be O(k) for k unique elements.
Trade-offs
Pros
Most efficient approach with a single pass over the data.
Combines counting and calculation, which can be slightly faster in practice than the two-pass method.
Cons
Requires extra space, similar to the two-pass approach.
Solutions
Solution
class Solution {public int numIdenticalPairs(int[] nums) { int ans = 0; int[] cnt = new int[101]; for (int x : nums) { ans += cnt[x]++; } return ans; }}/** * @param {number[]} nums * @return {number} */ var numIdenticalPairs = function (nums) { const cnt = Array(101).fill(0); let ans = 0; for (const x of nums) { ans += cnt[x]++; } return ans; };class Solution { public: int numIdenticalPairs ( vector < int >& nums ) { int ans = 0 ; int cnt [ 101 ]{}; for ( int & x : nums ) { ans += cnt [ x ] ++ ; } return ans ; } };class Solution : def numIdenticalPairs ( self , nums : List [ int ]) -> int : ans = 0 cnt = Counter () for x in nums : ans += cnt [ x ] cnt [ x ] += 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.