Solution Explanation: Counting Bad Pairs

The problem asks to find the number of "bad pairs" in an array nums. A bad pair (i, j) is defined where i < j and j - i != nums[j] - nums[i]. This condition essentially means the difference in indices doesn't match the difference in the values at those indices.

Approach: Efficient Counting using Hash Table

The core idea is to transform the condition for a bad pair to make counting more efficient. We can rewrite the inequality:

j - i != nums[j] - nums[i]

as:

i - nums[i] != j - nums[j]

This means we are interested in the difference between the index and the value at that index (i - nums[i]). If we find many pairs with the same difference, those pairs will be good pairs. Bad pairs are those where this difference is unique.

We can use a hash table (dictionary in Python, HashMap in Java, unordered_map in C++) to count the occurrences of each difference i - nums[i].

Algorithm:

1. Initialization: Create a hash table (cnt) to store the counts of each difference i - nums[i]. Initialize a variable ans (the total number of bad pairs) to 0.

2. Iteration: Iterate through the nums array using a loop with index i. For each element:

   • Calculate the difference diff = i - nums[i].
   • The number of good pairs formed by index i with indices before i is given by the current count of diff in cnt. All other pairs with i are bad pairs.
   • Add i - cnt[diff] to ans (This directly counts the bad pairs formed with i).
   • Increment the count of diff in cnt.

3. Return: After iterating through all elements, return ans.

Time and Space Complexity

• Time Complexity: O(n), where n is the length of nums. We iterate through the array once, and hash table operations (get, set, increment) are typically O(1) on average.

• Space Complexity: O(n) in the worst case. The hash table might store up to n distinct differences if all i - nums[i] values are unique.

Code Examples (with explanations inline):

Python:

from collections import Counter
 
class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        cnt = Counter()  # Use Counter for efficient counting
        ans = 0
        for i, x in enumerate(nums):  # Iterate with index i and value x
            diff = i - x
            ans += i - cnt[diff]  # Add the number of bad pairs involving current index i
            cnt[diff] += 1  # Increment the count of the difference
        return ans
 

Java:

import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public long countBadPairs(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        long ans = 0;
        for (int i = 0; i < nums.length; ++i) {
            int diff = i - nums[i];
            ans += i - cnt.getOrDefault(diff, 0); //getOrDefault handles cases where diff isn't in map yet.
            cnt.put(diff, cnt.getOrDefault(diff, 0) + 1);
        }
        return ans;
    }
}

C++:

#include <unordered_map>
#include <vector>
 
using namespace std;
 
class Solution {
public:
    long long countBadPairs(vector<int>& nums) {
        unordered_map<int, int> cnt;
        long long ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            int diff = i - nums[i];
            ans += i - cnt[diff];
            cnt[diff]++;
        }
        return ans;
    }
};

The other languages (Go, TypeScript) follow a very similar structure, using their respective hash table implementations. The core logic remains the same: efficient counting of differences to calculate bad pairs.