Count Number of Bad Pairs solution and explanation
Google
9 more videos on this problem
Count Number of Bad Pairs - Leetcode 2364 - PythonNeetCodeIO · 12:02 · 10K views
Count Number of Bad Pairs | 3 Ways | Intuition | Leetcode 2364 | codestorywithMIKcodestorywithMIK · 28:45 · 9K views
Count Number of Bad Pairs | Leetcode 2364Techdose · 13:06 · 5K views
2364. Count Number of Bad Pairs | leetcode daily challenge | shashcode | java | dsa | shashwatShashCode · 12:19 · 2K views
2364. Count Number of Bad Pairs | Hash MapAryan Mittal · 10:54 · 1K views
2364. Count Number of Bad Pairs (Leetcode Medium)Programming Live with Larry · 4:38 · 1K views
Leetcode 2364: Count Number of Bad PairsAlgorithms Casts · 8:53 · 1K views
Count Number of Bad Pairs | Leetcode 2364Ayushi Sharma · 14:09 · 1K views
Leetcode 2364. Count Number of Bad PairsElite Code · 19:05 · 436 views
2364. Count Number of Bad Pairs | Leetcode Daily ChallengeEthos Typos · 10:13 · 377 views
The problem
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.
Example 1:
Input: nums = [4,1,3,3] Output: 5 Explanation: The pair (0, 1) is a bad pair since 1 - 0 != 1 - 4. The pair (0, 2) is a bad pair since 2 - 0 != 3 - 4, 2 != -1. The pair (0, 3) is a bad pair since 3 - 0 != 3 - 4, 3 != -1. The pair (1, 2) is a bad pair since 2 - 1 != 3 - 1, 1 != 2. The pair (2, 3) is a bad pair since 3 - 2 != 3 - 3, 1 != 0. There are a total of 5 bad pairs, so we return 5.
Example 2:
Input: nums = [1,2,3,4,5] Output: 0 Explanation: There are no bad pairs.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109
Approach overview
Problem Overview: You are given an integer array nums. A pair of indices (i, j) with i < j is considered bad if j - i != nums[j] - nums[i]. The task is to count how many such bad pairs exist in the array.
Approach 1: Brute Force Pair Check (O(n²) time, O(1) space)
The most direct approach checks every pair of indices. Use two nested loops: the outer loop picks i and the inner loop checks all j > i. For each pair, compute j - i and nums[j] - nums[i]. If the values differ, increment the bad pair count. This approach is straightforward and useful for validating logic during development. However, it performs about n(n-1)/2 comparisons, which becomes too slow for large inputs.
Approach 2: Hash Map with Mathematical Transformation (O(n) time, O(n) space)
Rewrite the condition to reveal a useful pattern. A pair is good when j - i = nums[j] - nums[i]. Rearranging gives nums[j] - j = nums[i] - i. This means two indices form a good pair when the value nums[k] - k is the same for both indices. Instead of directly counting bad pairs, count good pairs using a frequency map.
Iterate through the array once. For each index i, compute key = nums[i] - i. Use a hash table to track how many times this key has appeared. Every previous occurrence forms a good pair with the current index, so add that frequency to the good pair count. Update the map afterward. Finally, compute total possible pairs using n * (n - 1) / 2 and subtract the number of good pairs to get the bad pair count.
This optimization relies on a simple math transformation and efficient lookups using a hash map. The algorithm scans the array once and performs constant-time hash operations, reducing the complexity from quadratic to linear.
Recommended for interviews: The hash map approach is the expected solution. Interviewers want to see the algebraic transformation nums[i] - i that converts the pair condition into a frequency counting problem. Explaining the brute force solution first shows understanding of the problem, while deriving the O(n) hash map solution demonstrates algorithmic insight.
Approach 1: Brute Force Approach
This approach involves checking every possible pair of indices (i, j) where i < j and seeing if they satisfy the condition j - i != nums[j] - nums[i]. This will involve nested loops and checking the condition directly.
def count_bad_pairs(nums):
bad_pairs = 0
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if j - i != nums[j] - nums[i]:
bad_pairs += 1
return bad_pairs
nums = [4, 1, 3, 3]
print(count_bad_pairs(nums))public class BadPairs {
public static int countBadPairs(int[] nums) {
int badPairs = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (j - i != nums[j] - nums[i])
badPairs++;
}
}
return badPairs;
}
public static void main(String[] args) {
int[] nums = {4, 1, 3, 3};
System.out.println(countBadPairs(nums));
}
}#include <iostream>
#include <vector>
int countBadPairs(std::vector<int>& nums) {
int badPairs = 0;
for (size_t i = 0; i < nums.size(); ++i) {
for (size_t j = i + 1; j < nums.size(); ++j) {
if (j - i != nums[j] - nums[i])
badPairs++;
}
}
return badPairs;
}
int main() {
std::vector<int> nums = {4, 1, 3, 3};
std::cout << countBadPairs(nums) << std::endl;
return 0;
}function countBadPairs(nums) {
let badPairs = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (j - i !== nums[j] - nums[i])
badPairs++;
}
}
return badPairs;
}
let nums = [4, 1, 3, 3];
console.log(countBadPairs(nums));#include <stdio.h>
int countBadPairs(int* nums, int numsSize) {
int badPairs = 0;
for (int i = 0; i < numsSize; i++) {
for (int j = i + 1; j < numsSize; j++) {
if (j - i != nums[j] - nums[i])
badPairs++;
}
}
return badPairs;
}
int main() {
int nums[] = {4, 1, 3, 3};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d", countBadPairs(nums, size));
return 0;
}using System;
class Program {
public static int CountBadPairs(int[] nums) {
int badPairs = 0;
for (int i = 0; i < nums.Length; i++) {
for (int j = i + 1; j < nums.Length; j++) {
if (j - i != nums[j] - nums[i])
badPairs++;
}
}
return badPairs;
}
static void Main() {
int[] nums = {4, 1, 3, 3};
Console.WriteLine(CountBadPairs(nums));
}
}The Python solution uses a double-loop structure to verify each pair of indices. As it identifies any index pair (i, j) where the condition doesn’t hold, it counts up. This simplistic method has O(n^2) time complexity because every pair is checked once.
Time Complexity: O(n^2)
Space Complexity: O(1)
Approach 2: Optimized Approach using Hash Maps
To improve upon the brute force method, this approach introduces the concept of a hash map (or dictionary) to track the counts of differences calculated by "nums[i] - i". Using this, we can efficiently compute the number of good pairs and then derive the number of bad pairs from it.
def count_bad_pairs(nums):
from collections import defaultdict
diff_count = defaultdict(int)
bad_pairs = 0
for i, num in enumerate(nums):
diff = num - i
bad_pairs += i - diff_count[diff]
diff_count[diff] += 1
return bad_pairs
nums = [4, 1, 3, 3]
print(count_bad_pairs(nums))import java.util.HashMap;
public class BadPairs {
public static int countBadPairs(int[] nums) {
HashMap<Integer, Integer> diffCount = new HashMap<>();
int badPairs = 0;
for (int i = 0; i < nums.length; i++) {
int diff = nums[i] - i;
badPairs += i - diffCount.getOrDefault(diff, 0);
diffCount.put(diff, diffCount.getOrDefault(diff, 0) + 1);
}
return badPairs;
}
public static void main(String[] args) {
int[] nums = {4, 1, 3, 3};
System.out.println(countBadPairs(nums));
}
}#include <iostream>
#include <vector>
#include <unordered_map>
int countBadPairs(const std::vector<int>& nums) {
std::unordered_map<int, int> diffCount;
int badPairs = 0;
int n = nums.size();
for (int i = 0; i < n; i++) {
int diff = nums[i] - i;
badPairs += i - diffCount[diff];
diffCount[diff]++;
}
return badPairs;
}
int main() {
std::vector<int> nums = {4, 1, 3, 3};
std::cout << countBadPairs(nums) << std::endl;
return 0;
}function countBadPairs(nums) {
const diffCount = new Map();
let badPairs = 0;
for (let i = 0; i < nums.length; i++) {
const diff = nums[i] - i;
const currentCount = diffCount.has(diff) ? diffCount.get(diff) : 0;
badPairs += i - currentCount;
diffCount.set(diff, currentCount + 1);
}
return badPairs;
}
let nums = [4, 1, 3, 3];
console.log(countBadPairs(nums));#include <stdio.h>
#include <stdlib.h>
int countBadPairs(int* nums, int numsSize) {
int* hash = calloc(numsSize, sizeof(int));
int badPairs = 0, goodPairs = 0;
for (int i = 0; i < numsSize; i++) {
int diff = nums[i] - i;
badPairs += i - hash[diff];
hash[diff]++;
}
free(hash);
return badPairs;
}
int main() {
int nums[] = {4, 1, 3, 3};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d", countBadPairs(nums, size));
return 0;
}using System;
using System.Collections.Generic;
class Program {
public static int CountBadPairs(int[] nums) {
Dictionary<int, int> diffCount = new Dictionary<int, int>();
int badPairs = 0;
for (int i = 0; i < nums.Length; i++) {
int diff = nums[i] - i;
if (!diffCount.ContainsKey(diff))
diffCount[diff] = 0;
badPairs += i - diffCount[diff];
diffCount[diff]++;
}
return badPairs;
}
static void Main() {
int[] nums = {4, 1, 3, 3};
Console.WriteLine(CountBadPairs(nums));
}
}By leveraging Python's defaultdict, this efficient solution maintains a tally of how many of each difference exists as it iterates the list. Each previously encountered difference insightfully contributes to quickly determining bad pairs, achieving an O(n) time complexity.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Equation Transformation + Hash Table
According to the problem description, for any i \lt j, if j - i neq nums[j] - nums[i], then (i, j) is a bad pair.
We can transform the equation into i - nums[i] neq j - nums[j]. This suggests using a hash table cnt to count the occurrences of i - nums[i].
While iterating through the array, for the current element nums[i], we add i - cnt[i - nums[i]] to the answer, and then increment the count of i - nums[i] by 1.
Finally, we return the answer.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.
function countBadPairs(nums: number[]): number {
const cnt = new Map<number, number>();
let ans = 0;
for (let i = 0; i < nums.length; ++i) {
const x = i - nums[i];
ans += i - (cnt.get(x) ?? 0);
cnt.set(x, (cnt.get(x) ?? 0) + 1);
}
return ans;
}func countBadPairs(nums []int) (ans int64) {
cnt := map[int]int{}
for i, x := range nums {
x = i - x
ans += int64(i - cnt[x])
cnt[x]++
}
return
}use std::collections::HashMap;
impl Solution {
pub fn count_bad_pairs(nums: Vec<i32>) -> i64 {
let mut cnt: HashMap<i32, i64> = HashMap::new();
let mut ans: i64 = 0;
for (i, &num) in nums.iter().enumerate() {
let x = i as i32 - num;
let count = *cnt.get(&x).unwrap_or(&0);
ans += i as i64 - count;
*cnt.entry(x).or_insert(0) += 1;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2) |
| Optimized Approach using Hash Maps | Time Complexity: O(n) |
| Equation Transformation + Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Enumeration | O(n²) | O(1) | Small input sizes or verifying logic during initial implementation |
| Hash Map with nums[i] - i Transformation | O(n) | O(n) | General case and interview settings where linear time is required |
Frequently asked questions
Is Count Number of Bad Pairs easy or hard?
Count Number of Bad Pairs is rated Medium difficulty. The brute force idea is simple, but recognizing the algebraic transformation nums[i] - i and converting the problem into a hash map counting task requires pattern recognition common in mid-level interview problems.
Count Number of Bad Pairs Python/Java solution
The standard implementation uses a dictionary in Python or a HashMap in Java. During a single pass through the array, compute nums[i] - i, update its frequency in the map, and accumulate good pair counts. The final answer is total pairs minus the number of good pairs.
How to solve Count Number of Bad Pairs in O(n)?
Compute key = nums[i] - i while iterating through the array. Use a hash map to count how many times this key has appeared before. Each previous occurrence forms a good pair with the current index. Track total good pairs and subtract them from n*(n-1)/2 to obtain the number of bad pairs in O(n) time.
What is the best approach for Count Number of Bad Pairs?
The optimal approach uses a hash map with a mathematical transformation. By rewriting the condition j - i = nums[j] - nums[i] into nums[i] - i, you can count good pairs with the same value using a frequency map. The number of bad pairs is then total pairs minus good pairs. This runs in O(n) time with O(n) space.
Is Count Number of Bad Pairs asked at Google/Amazon/Meta?
This problem reflects a common interview pattern involving hash maps, pair counting, and mathematical transformations. Variations of this pattern appear in interviews at companies like Amazon, Google, and Meta where candidates must optimize pair comparisons from O(n^2) to O(n).
What data structure is used in Count Number of Bad Pairs?
The optimized solution primarily uses a hash table (hash map) to store the frequency of values nums[i] - i. This allows constant-time lookups and efficient counting of previously seen matching values while scanning the array.
What is the time complexity of Count Number of Bad Pairs?
The brute force approach checks every pair and runs in O(n^2) time. The optimized solution processes the array once while maintaining a hash map of values nums[i] - i, giving O(n) time complexity and O(n) space complexity.