Count Bad Pairs — Complement Counting With a Frequency Hashmap

Problem Statement#

You are given a 0-indexed integer array nums. A pair of indices (i, j) is a bad pair if i < j and j - i != nums[j] - nums[i]. Return the total number of bad pairs.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9

Input:  nums = [4,1,3,3]
Output: 5

Input:  nums = [1,2,3,4,5]
Output: 0

Why This Problem Matters#

LeetCode 2364 is a high-signal hashmap interview problem that Google, Amazon, and Meta deploy on phone screens. It is medium-rated, but its real teaching value is the "flip the problem" move: instead of counting bad pairs directly, count good pairs and subtract from the total n*(n-1)/2.

The algebraic trick that unlocks the hashmap is rearranging j - i == nums[j] - nums[i] into nums[i] - i == nums[j] - j. Once the equality is in that form, a frequency map of nums[k] - k lets you count good pairs in a single pass.

This is a hash table FAANG pattern that reappears in "count pairs with absolute difference k", "subarrays with equal sum", and many array problems. Recognizing it once means recognizing it everywhere.

The Core Insight#

A pair is good when nums[i] - i == nums[j] - j. Group indices by their key nums[k] - k. Within each group of size g, the number of good pairs is g * (g - 1) / 2. Subtract the sum of these from the total pair count to get bad pairs.

We can also count good pairs in a streaming fashion: scan left to right, and for index j add the count of indices i < j already seen with the same key.

Visual Dry Run#

nums = [4,1,3,3]. Key for index k is nums[k] - k.

Good pairs = 1, total pairs = 4*3/2 = 6, bad = 6 - 1 = 5.

Solution (Optimal)#

from collections import defaultdict
 
class Solution:
    def countBadPairs(self, nums: list[int]) -> int:
        n = len(nums)
        total_pairs = n * (n - 1) // 2
        good = 0
        seen = defaultdict(int)
        for i, v in enumerate(nums):
            key = v - i
            good += seen[key]
            seen[key] += 1
        return total_pairs - good

var countBadPairs = function(nums) {
    const n = nums.length;
    const totalPairs = n * (n - 1) / 2;
    let good = 0;
    const seen = new Map();
    for (let i = 0; i < n; i++) {
        const key = nums[i] - i;
        good += seen.get(key) || 0;
        seen.set(key, (seen.get(key) || 0) + 1);
    }
    return totalPairs - good;
};

Time: O(n) — single pass with O(1) hashmap operations. Space: O(n) — the frequency map can hold up to n distinct keys.

Common Mistakes#

• Counting bad pairs directly in O(n^2), missing the complement-counting trick.
• Using i - nums[i] instead of nums[i] - i. Both work because the equality is symmetric, but mixing the two leads to off-by-one bugs.
• Forgetting that the total pair count is n*(n-1)/2, not n*n or n*(n-1).
• Using a 32-bit integer for the answer in JavaScript or Java; n up to 10^5 makes the total approach 5 * 10^9.
• Updating the map before adding to good, double-counting the current index against itself.

Interview Tips#

• Walk through the algebra on the whiteboard. Saying "I will rewrite the predicate" signals strong fundamentals.
• After deriving nums[i] - i == nums[j] - j, name it: "this is a frequency-counting hashmap pattern."
• Mention that the same shape solves "count equivalent pairs by transformation T(x)".
• Use 64-bit integers in any language where overflow is a concern.

Follow-up Questions#

• What if you need to count pairs where the predicate is j - i == 2 * (nums[j] - nums[i])? Hint: rearrange to 2*nums[i] - i == 2*nums[j] - j and hash that.
• What if the array is updated dynamically? Hint: maintain the frequency map and update good on each insert/delete.
• What if you must return the bad pairs themselves? Hint: track index lists per key, then enumerate the complement.
• How would you parallelize this? Hint: shard by key hash; counts are associative.
• What if nums[i] is a 64-bit integer? Hint: Python is fine; in JavaScript use BigInt.

Key Takeaways#

• LeetCode 2364 teaches the complement-counting hashmap pattern.
• Rewrite j - i == nums[j] - nums[i] as nums[i] - i == nums[j] - j and hash that key.
• Total pairs is n*(n-1)/2; bad = total - good.
• One pass, O(n) time, O(n) space — Google-grade efficient.
• Watch for integer overflow in 32-bit languages.
• The "flip the problem" trick generalizes across array, string, and graph problems.
• Memorize this as the canonical hashmap interview shape: pair counting via a transformation key.