[Leetcode] – Number of Good Pairs Solution

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.

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.

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.

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.

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: