Program to Count Number of Good Pair.

Given an integer array num of size n, return the count of possible good pairs. A pair of elements is called a good pair if (num[i] == num[j]) and i < j.

Example:

Example 1:
Input: num[] = {2, 1, 3, 2, 2, 3};
Output: 4

Explanation: 
There are four good pairs (0, 3), (0, 4), (2, 5) and (3, 4)

Example 2:
Input: num[] = {3, 3, 3, 3}
Output: 6

Approach 1: Brute Force Solution.

Take a count variable and initialize it with 0. Run two nested for loops for each element of the array, pick each element one by one and then compare it with the remaining element and then keep on increasing the count variable whenever the given condition is satisfied.

C++ Solution Code:

/*C++ code for count number of good pairs*/
#include<bits/stdc++.h>
using namespace std;

int goodPairs(vector<int> &num){
    int count = 0;

    for(int i = 0; i < num.size(); i++){
        for(int j = i+1; j < num.size(); j++){
            if(num[i] == num[j])
              count++;
        }
    }
    return count;
}

int main(){
    vector<int> num = {2, 1, 3, 2, 2, 3};

    int count = goodPairs(num);
    cout<<"Number of Good Pairs: "<<count;

    return 0;   
}

Output:

Number of Good Pairs: 4

Time Complexity: Running two nested loops for n elements takes O(n^2) time complexity.
Space Complexity: No extra space is required in the above solution so space complexity is O(1).

Approach 2: Using Hash Map.

You can optimize the previous solution by using a hash map to get the count of each unique element of the array.

Given num = [2, 1, 3, 2, 2, 3]

Structure of map:

Key      Value(count)

 2          3 (Value 2 appears 3 times)

 1          1 (Value 1 appears 1 times)

 3          2 (Value 3 appears 2 times)

When you have n number of similar values then it can create [n*(n-1)/2] number of unique good pairs.

[3, 3, 3, 3]

Number of Good Pairs = 4*(4-1)/2 = 6

Similarly, you can calculate the number of unique good pairs for each value of the map and sum them up to get the total number of good pairs possible from all array elements.

Key      Value(count)      Good Pairs

 2          3            [3*(3-1)/2 = 3]

 1          1            [1*(1-1)/2 = 0]

 3          2            [2*(2-1)/2 = 1]

Total number of Good Pairs = 3+0+1 = 4

C++ Solution Code:

/*C++ code for count number of good pairs(Optimized)*/
#include<bits/stdc++.h>
using namespace std;

int goodPairs(vector<int> &num){
    int count = 0;
    unordered_map<int, int> mp;

    //Storing count of each unique element
    for(int i = 0; i < num.size(); i++){
        mp[num[i]]++;
    }

    //counting good pairs
    for(auto i:mp){
        int n = i.second;
        count += (n*(n-1))/2;
    }
    return count;
}

int main(){
    vector<int> num = {2, 1, 3, 2, 2, 3};

    int count = goodPairs(num);
    cout<<"Number of Good Pairs: "<<count;

    return 0;   
}

Output:

Number of Good Pairs: 4

Time Complexity: We run two separate loops one for storing the count in the map and the next loop for counting good pairs so the average time complexity will be O(n).
Space Complexity: We are using one map to store the count of elements so space complexity will be O(n).

Next:

(getButton) #text=(Count Number of Elements Smaller than Current Element) #icon=(link) #color=(#2339bd)

Program to Count Number of Good Pair.

Approach 1: Brute Force Solution.

Approach 2: Using Hash Map.

No comments:

Post a Comment