Count Bad Pairs — Complement Counting with HashMap

Problem 186 · Count Bad Pairs

Difficulty: Medium · Pattern: Complement Map

A pair (i,j) with i<j is bad if j-i ≠ nums[j]-nums[i]. Count all bad pairs.

Intuition

Rearrange: a pair is good if nums[j]-j == nums[i]-i. Count good pairs via a frequency map of nums[i]-i, then bad = total - good.

Solutions

// C++
long long countBadPairs(vector<int>& nums) {
    long long n = nums.size();
    unordered_map<int,long long> cnt;
    long long good = 0;
    for (int i = 0; i < n; i++) {
        int key = nums[i] - i;
        good += cnt[key];
        cnt[key]++;
    }
    return n*(n-1)/2 - good;
}

// Java
public long countBadPairs(int[] nums) {
    long n = nums.length, good = 0;
    Map<Integer,Long> cnt = new HashMap<>();
    for (int i = 0; i < n; i++) {
        int key = nums[i] - i;
        good += cnt.getOrDefault(key, 0L);
        cnt.merge(key, 1L, Long::sum);
    }
    return n*(n-1)/2 - good;
}

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

# Python
from collections import defaultdict
def countBadPairs(nums):
    n = len(nums)
    cnt = defaultdict(int)
    good = 0
    for i, x in enumerate(nums):
        good += cnt[x - i]
        cnt[x - i] += 1
    return n*(n-1)//2 - good

Complexity

Time: O(n)
Space: O(n)