Home Arrays [Leetcode] – Number of Good Pairs Solution

[Leetcode] – Number of Good Pairs Solution

by nikoo28
0 comment 5 mins read

Always make sure that we understand the problem statement first. There is an array of integers nums and we need to determine the number of good pairs. A pair (i , j ) is said to be good, if nums[i] == nums[j] and i < j. We need to determine how many pairs can we form that hold this condition.

Let us look at some sample test cases:

Input: nums = [ 1 , 2 , 3 , 1 , 1 , 3 ]
Output: 4
Explanation:
There are 4 good pairs. (0 , 3) , (0 , 4) , (3 , 4) , (2 , 5)
nums[0] = 1, which is equal to nums[3] = 1 && 0 < 3
nums[2] = 3, which is equal to nums[5] = 3 && 2 < 5

Input: nums = [ 1 , 2 , 3 ]
Output: 0
Explanation:
The array does not have any element that are equal to each other.

figure showing sample test case and indexes
Fig: Sample test case

Brute Force Method:

The most straight forward or Brute Force approach to solve this problem will be:

  • Start with each element.
  • Compare it to every other number in the array.
  • If they are same, check if left index is smaller than right index.
  • Add the value of i and j to your number of good pairs.
  • Repeat this process for every number in the array.

At the end, we have the total number of good pairs. This method will give a correct answer but it is not scalable. As the size of array grows, the number of comparisons that we do will also keep on increasing. We waste a lot of time just to iterate through the array.

figure showing brute force comparisons
Fig: Brute force comparisons

Time Efficient Method:

In the above method, we are facing a problem because of the time the process takes. Hence, to find an efficient solution we try to make sure that we are not iterating through the array again and again. One idea is that more the count of a particular integer, more the number of good pairs we can form.

Counting sort can be helpful in such a scenario.

For a given test case like: [ 1 , 2 , 3 , 1 , 1 , 3 , 5 , 2 , 5 , 1 , 3 ]. We can initialize a frequency array that stores the frequency of each number.

Fig: Frequency array

Iterate through the array, and keep on incrementing the counts in the frequency array. Once we have iterated through the array, we know exactly how many 1's we have in the array, how many 2's we have, and so on.

frequency array showing the count of each element
Fig: Populating the frequency array
Calculating the number of good pairs:

Determining this involves basic maths and finding the combinations possible with 2 numbers.

^nC_r = \frac{n!}{(n-r)!}
Total\ pairs =\ ^4C_2\ +\ ^2C_2\ +\ ^3C_2\ +\ ^0C_2\ +\ ^2C_2\ +\ ^0C_2\ 

Code:

public int numIdenticalPairs(int[] nums) { // Calculate the frequency of each number int[] count = new int[102]; for (int num : nums) { count[num]++; } int totalCount = 0; // Caclulate total number of pairs possible for (int i : count) { totalCount += ((i) * (i-1))/2; } return totalCount; }
Code language: Java (java)

Time Complexity: O(n)
Space Complexity: O(n)

You can also find the code and test cases on GitHub.

Video Explanation:

You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More