1512. Number of Good Pairs

(LeetCode easy question)

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 <= 100
• 1 <= nums[i] <= 100

Let us first understand the question, what it means. Let us take the first example nums = [1,2,3,1,1,3].

Now the question says if nums[i]==nums[j] and i<j then count the number of pairs satisfying the given criteria. So let us find out how many such pairs exist,

nums[0] == nums[3] and 0 < 3 , count = 1

nums[0] ==nums[4] and 0 < 4 , count = 2

nums[3] ==nums[4] and 3 < 4 , count = 3

nums[2] == nums[5] and 2 < 5 , count = 4

So the total count here is 4 and so is the desired answer.

So the first basic approach that comes to my mind is the brute force approach. Let us discuss it below.

Brute-Force approach

Here I will use two loops, one inside the other, and will check if the array elements satisfy the given condition. Seems easy right? Let us code it.

class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        int count = 0;
        for(int i=0;i<nums.size()-1;i++)
        {
            for(int j=i+1;j<nums.size();j++)
            {
                if(i<j && nums[i]==nums[j])
                    count++;
            }
        }
        return count;
    }
};

I have used a count variable to keep track of the total number of such pairs. Can you say anything about the time & space complexity?

Well since I am using two loops one inside the other, for the first element there will be (n-1) comparisons , for the second (n-2), and so on...

You will get time complexity as O(n*n) and space complexity is O(1) because I am not using any extra space.

Let us now move to an optimized approach. I think we can optimize the time complexity here to a single traversal.

Optimized Approach

If 3 elements are the same, how many pairs satisfying the above criteria would exist? Do you remember the maths classes? It would be 3C2 = 3!/2!*1! .

So what if we get the count for all the elements separately and then perform this function on each of them and simultaneously keep adding the values.

Let us try this approach out.

Eg : [1,2,3,1,13]

count of 1’s = 3

count of 2’s = 1(no pair will exist for this because 1C2 is not possible)

count of 3’s = 2

So now total possible pairs ,

1’s = 3!/2!*1! = 3

3’s = 2!/2!*0! = 1

so total pairs = 3 + 1 = 4 pairs exist which is the required answer.

So now let us code it.

I am using a hash map to store the frequency of each of the elements in the array. For all the frequencies that I have stored, I iterate over and apply the formula to calculate the pairs and keep adding them till I reach the end.

So what do you think is the time complexity? Since I am traversing the array twice it will be O(2*n) which means that I am using two passes. It will approximate O(n) and Space complexity is O(n) because I am using a hash map to store the frequencies.

class Solution {
public:
   
    int numIdenticalPairs(vector<int>& nums) {
      
        int count = 0;
        unordered_map<int,int>ans;
        for(int i=0;i<nums.size();i++)
        {
            ans[nums[i]]++;
        }
        
        for(auto it: ans)
        {
            int val = it.second;
            count = count + (val*(val-1))/2;
        }
        return count;
    }
};

Hope this helps in understanding clearly. Till then keep coding & keep learning!!💻🙌

Since you enjoyed reading my blog , why not buy me a coffee and supoort my work here!! https://www.buymeacoffee.com/sukanyabharati ☕