Number of Good Pairs Leetcode Solution

Difficulty Level Easy
Frequently asked in Amazon Microsoft
algorithms Array coding Hashing Interview interviewprep LeetCode LeetCodeSolutions MathViews 8531

Problem Statement

In this problem an array of integers is given and we have to find out the count of total number of good pairs (a[i], a[j]) where a[i]=a[j].

Example

nums = [1,2,3,1,1,3]
4

Explanation:   There are 4 good pairs at indices (0,3), (0,4), (3,4), (2,5) .

[1,1,1,1]
6

Explanation:   Each pair in the array are good.

Approach (Brute Force)

In the given problem we can use two loop, one for a[i] and second for a[j] of the pair. In this nested loop we will iterate for all possible combination for the pair (a[i], a[j]) and check whether a[i] is equal to a[j] or not.

Algorithm:

1. Create a count variable and initialize with zero.
2. Run a nested loop, outer loop for a[i] from i=0 to i=n-1 and inner loop for a[j] from j=i+1 to j=n-1.
3. If a[i]=a[j], add current pair to count by incrementing its value by 1.
4. Return the value of count variable.

Implementation for Number of Good Pairs Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

int numIdenticalPairs(vector<int>& nums) 
{
       int res = 0;
       for(int i=0;i<nums.size();i++)
           for(int j=i+1;j<nums.size();j++)
               if(nums[i]==nums[j]) res++;
               
       return res;
}

int main() 
{
    vector<int> nums={1,2,3,1,1,3};
  
  cout<<numIdenticalPairs(nums)<<endl;

  return 0; 
}
4

Java Program

import java.lang.*;

class GoodPairs
{  
    public static int numIdenticalPairs(int[] nums) 
    {
        int res = 0;
        for(int i=0;i<nums.length;i++)
          for(int j=i+1;j<nums.length;j++)
             if(nums[i]==nums[j])   res++;

        return res;
    }

    public static void main(String args[])
    {
       int nums[]={1,2,3,1,1,3};
  
       System.out.println( numIdenticalPairs(nums));
        
    }
}
4

Complexity Analysis for Number of Good Pairs Leetcode Solution

Time Complexity

O(N^2) : Where N is the size of the given array. As we are using two loops and checking all combinations of elements at index i and j, the time complexity will be O(N^2).

Space Complexity 

O(1) : We are not using any extra memory.

 

Approach (Optimized)

We can optimize the solution by using Hash Map. There is no use of iterating over all combinations of pairs i*j times. We have to count only the equal elements.
i.e. If we have count of a particular element in the array we can calculate total number of ways of picking any two elements in this set of similar elements.
For this what we can do is, we can iterate from the 1st element and update the count of each element at every step.
Whenever we find a element we will check how many similar elements have already been present before this element using a count map variable. So that it can make pair with all those previous occurred elements.
We will add that count to our result and update (increment) the count of current element by +1.

Number of Good Pairs Leetcode Solution

Algorithm :
1. Create a Has Map of Integer and Integer whose key is the element and value is the current count of that element.
2. Run a for loop for each element form i=0 to n-1.
3. Find the count(a[i]) before putting it into the map and add this value to the res.
4. Now update the count of a[i] as count(a[i]) = count(a[i]) + 1.
5. Return the value of res.

Implementation for Number of Good Pairs Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

int numIdenticalPairs(vector<int>& nums) 
{
    int res = 0;
    unordered_map<int, int> count;
    for (int a: nums) 
    {
        res += count[a]++;
    }
  
    return res;
}

int main() 
{
    vector<int> nums={1,2,3,1,1,3};
  
  cout<<numIdenticalPairs(nums)<<endl;

  return 0; 
}
4

Java Program

import java.lang.*;
import java.util.*;

class GoodPairs
{  
    public static int numIdenticalPairs(int[] nums) 
    {
        int res = 0;
        Map<Integer,Integer> count= new HashMap<Integer,Integer>();
        for (int a: nums)
        {
            int cur=count.getOrDefault(a,0);
            res += cur;
            count.put(a,cur+1);
        }
        return res;
    }

    public static void main(String args[])
    {
       int nums[]={1,2,3,1,1,3};
  
       System.out.println( numIdenticalPairs(nums));
        
    }
}
4

Complexity Analysis for Number of Good Pairs Leetcode Solution

Time Complexity

O(N) : As we are doing constant work in updating the count of each element using Hash Map, therefore time complexity will be O(N).

Space Complexity 

O(N) : We are using a Hash Map to store the count of each unique elements. There can be N different elements in worst case.

Translate »