Count Number of Bad Pairs

medium hashing hash map counting

Problem

Given a 0-indexed integer array nums, a pair of indices (i, j) with i < j is a bad pair when j - i != nums[j] - nums[i]. Return the total number of bad pairs in nums.

Inputnums = [4,1,3,3]

Output5

There are 6 pairs total; only (1,3) with key 0 forms a good pair, so 6 − 1 = 5 are bad.

Inputnums = [1,2,3,4,5]

Output0

Every pair satisfies j − i = nums[j] − nums[i], so there are no bad pairs.

nums (comma-separated)

def count_bad_pairs(nums):
    n = len(nums)
    total = n * (n - 1) // 2
    count = {}
    good = 0
    for i in range(n):
        key = nums[i] - i
        good += count.get(key, 0)
        count[key] = count.get(key, 0) + 1
    return total - good

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

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

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

Explanation

A pair is good exactly when j - i == nums[j] - nums[i]. The number of bad pairs is then just all pairs minus the good pairs, so we only need to count good pairs efficiently.

The key trick is to rearrange the equation. Move the indices to one side: j - i == nums[j] - nums[i] becomes nums[i] - i == nums[j] - j. So a pair is good precisely when the two indices share the same value of nums[k] - k.

Define key(k) = nums[k] - k. Two indices form a good pair if and only if they have the same key. So we sweep left to right keeping a hash map count of how many earlier indices produced each key.

At index i we compute its key, then add count[key] to good — every earlier index with the same key pairs with i. Then we record i by incrementing count[key] for future indices.

Total pairs is n·(n−1)/2. The answer is total − good. This runs in a single pass: O(n) time and O(n) space.

For nums = [4,1,3,3] the keys are 4, 0, 1, 0. Only indices 1 and 3 share a key (0), giving 1 good pair, so the answer is 6 − 1 = 5.

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