Count Number of Bad Pairs

Leetcode Problem:

• Count Number of Bad Pairs

Summary

• The problem requires to find the total number of bad pairs in a given integer array
• A bad pair is defined as a pair of indices (i, j) where i < j and j - i!= nums[j] - nums[i].

Approach

• The approach used in the solution is to first modify the input array by adding the difference between the current index and the total length of the array to each element
• This is done to simplify the calculation of bad pairs
• Then, a hashmap is used to store the frequency of each modified element
• Finally, the total number of bad pairs is calculated by subtracting the sum of the first 'N' natural numbers (where N is the length of the array) from the total possible pairs and subtracting the sum of the frequencies of each modified element multiplied by the frequency minus one divided by two.

Complexity

• O(N) where N is the length of the input array

Explain

• The solution starts by modifying the input array by adding the difference between the current index and the total length of the array to each element
• This is done to simplify the calculation of bad pairs
• Then, a hashmap is used to store the frequency of each modified element
• The total number of bad pairs is calculated by subtracting the sum of the first 'N' natural numbers (where N is the length of the array) from the total possible pairs and subtracting the sum of the frequencies of each modified element multiplied by the frequency minus one divided by two
• This is because a pair is bad if the difference between the two elements is not equal to the difference between their indices
• By using the hashmap, we can efficiently count the number of bad pairs.

Solution Code:

class Solution {
public:
    unordered_map map;
    long long countBadPairs(vector& nums) {
        int N = nums.size();
        for(int i = 0 ; i < N; i++){
            nums[i] += N - i;
        }
        for(int i = 0 ; i < N; i++){
            map[nums[i]]++;
        }
        long long cnt = 0;
        for(auto iter : map){
            if(iter.second >= 2){
                cnt += ((iter.second) * (iter.second-1)) >> 1;
            }
        }
        return (((long long)N * (N-1)) >> 1) - cnt;
    }
};