Count Number of Bad Pairs — Medium Problem & Solution

Problem statement

A pair of indices (i, j) with i < j is bad when j - i != nums[j] - nums[i].

Return the number of bad pairs.

Example 1

Input: nums = [4,1,3,3]
Output: 5
Explanation: Of the six pairs only (1,3) is good, since 3 - 1 equals nums[3] - nums[1].

Example 2

Input: nums = [1,2,3,4,5]
Output: 0
Explanation: Every pair satisfies the equality, so none is bad.

Example 3

Input: nums = [7,7]
Output: 1

Constraints

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 1000000000

How to solve Count Number of Bad Pairs

Complementary counting. The good condition rearranges into an equality between two independent per-index quantities, so a single tally counts the good pairs and the rest are bad.

Approach

1. The total number of pairs is n * (n - 1) / 2.
2. Sweep the array keeping a tally of the key nums[k] - k; before inserting, add the current tally to the good count.
3. Return total - good.

Why it works

j - i == nums[j] - nums[i] is equivalent to nums[i] - i == nums[j] - j, so the good pairs are exactly the equal-key pairs. Counting before inserting attributes each pair to its later index once.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• nums[k] - k can be negative, so a plain array index will not do — use a hash map.
• n * (n - 1) / 2 overflows 32 bits once n passes about 65000; at the stated limit it is safe, but the habit matters.

Reference solution

Python

from typing import List

def countBadPairs(nums: List[int]) -> int:
    seen = {}
    good = 0
    for i, x in enumerate(nums):
        key = x - i
        good += seen.get(key, 0)
        seen[key] = seen.get(key, 0) + 1
    n = len(nums)
    return n * (n - 1) // 2 - good

JavaScript

var countBadPairs = function(nums) {
    var seen = {}, good = 0;
    var n = nums.length;
    for (var i = 0; i < n; i++) {
        var key = String(nums[i] - i);
        if (seen[key] !== undefined) good += seen[key];
        seen[key] = (seen[key] === undefined ? 0 : seen[key]) + 1;
    }
    return (n * (n - 1)) / 2 - good;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Count Number of Texts Medium
• Construct String With Repeat Limit Medium
• Minimum Number of Steps to Make Two Strings Anagram II Medium
• Count Vowel Substrings of a String Medium
• Minimum Length of String After Operations Medium
• Sum of Digit Differences of All Pairs Medium