Count Number of Bad Pairs

How it works

Rearranging the bad pair condition j - i != nums[j] - nums[i] gives us nums[j] - j != nums[i] - i. This means a pair is "good" when both elements have the same value of nums[k] - k. Instead of counting bad pairs directly, we count the total pairs and subtract the good pairs. Elements with the same transformed value form good pairs among themselves.

Steps

1. Use a hash map to track the frequency of each nums[i] - i value.
2. Keep a running total of pairs seen so far (which equals i at index i).
3. For each index, add the count of previously seen elements with the same transformed value to the good pairs count.
4. Update the hash map with the current transformed value.
5. Return total pairs minus good pairs.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Counting Bad Pairs Directly

Trying to count bad pairs directly with a hash map is error-prone. The cleaner approach is to count good pairs (where nums[i] - i == nums[j] - j) and subtract from total pairs.

Integer Overflow with Large Arrays

With n up to 10^5, the total number of pairs is n*(n-1)/2 which can exceed 32-bit integer limits. Use long or 64-bit integers for the result.

Forgetting the Algebraic Transformation

The key insight is rewriting j - i != nums[j] - nums[i] as nums[i] - i != nums[j] - j. Without this transformation, you cannot efficiently group elements using a hash map.

from typing import List
from collections import defaultdict

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        good_pairs = 0
        total_pairs = 0
        count = defaultdict(int)

        for i in range(len(nums)):
            total_pairs += i
            good_pairs += count[nums[i] - i]
            count[nums[i] - i] += 1

        return total_pairs - good_pairs

class Solution {
public:
    long long countBadPairs(vector<int>& nums) {
        unordered_map<int, int> count;
        long long total = 0, good = 0;
        for (int i = 0; i < nums.size(); i++) {
            int key = nums[i] - i;
            good += count[key];
            count[key]++;
            total += i;
        }
        return total - good;
    }
};