Count number of bad pairs

Array Hash Table Math Counting

54.2% acceptance

Feb 25, 2026

1789

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 in nums.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;


impl Solution {
  pub fn count_bad_pairs(nums: Vec<i32>) -> i64 {
    let n = nums.len() as i64;
    let total = n * (n - 1) / 2;
    let mut freq: HashMap<i32, i64> = HashMap::new();
    for (i, &v) in nums.iter().enumerate() {
      *freq.entry(v - i as i32).or_insert(0) += 1;
    }
    let good: i64 = freq.values().map(|&c| c * (c - 1) / 2).sum();
    total - good
  }
}