Count Number of Bad Pairs

Medium
679.

Count Number of Bad Pairs

Count Number of Bad Pairs is a medium coding problem on arrays, hash table and counting, asked in Amazon, Google and Swiggy interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var countBadPairs = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Number of Bad Pairs — Solution in Python, Java & C++

Count Number of Bad Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Number of Bad Pairs is a medium coding problem on arrays, hash table and counting, asked in Amazon, Google and Swiggy interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Counting
  • Asked at: Amazon, Google, Swiggy
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Count Number of Bad Pairs

  1. Hint 1

    Counting bad pairs directly is awkward; count the good ones and subtract from the total.

  2. Hint 2

    Rearrange j - i == nums[j] - nums[i] to nums[i] - i == nums[j] - j.

  3. Hint 3

    So good pairs are pairs with equal nums[k] - k, which one tally pass counts.

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

Java

public static int countBadPairs(int[] nums) {
    Map<Integer, Integer> seen = new HashMap<>();
    long good = 0;
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        int key = nums[i] - i;
        int c = seen.getOrDefault(key, 0);
        good += c;
        seen.put(key, c + 1);
    }
    return (int) ((long) n * (n - 1) / 2 - good);
}

C++

int countBadPairs(vector<int>& nums) {
    unordered_map<int, int> seen;
    long long good = 0;
    long long n = (long long) nums.size();
    for (int i = 0; i < (int) nums.size(); i++) {
        int key = nums[i] - i;
        good += seen[key];
        seen[key]++;
    }
    return (int) (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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets