Count Number of Bad Pairs - Solution & Explanation
Problem Statement
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.
The C solution uses two nested loops to iterate through all pairs of indices. The outer loop iterates through each element, and the inner loop checks for every element succeeding it. If the condition for a bad pair is satisfied, we increment the counter. The solution is straightforward but not optimal for large inputs due to its O(n^2) complexity.
Complexity
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.
The C implementation uses an array to simulate the hash map functionality, storing differences and their occurrences. Each difference is used to quickly calculate how many good & bad pairs exist as the input is processed. This efficient algorithm reduces time complexity to nearly O(n) via its single pass nature.
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.
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 | ā |
Detailed 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 |
Video Solution
Count Number of Bad Pairs - Leetcode 2364 - Python ā¢ NeetCodeIO ā¢ 10,974 views views
Watch 9 more video solutions āFrequently Asked Questions
Is Count Number of Bad Pairs easy or hard?
Count Number of Bad Pairs Python/Java solution
How to solve Count Number of Bad Pairs in O(n)?
What is the best approach for Count Number of Bad Pairs?
Is Count Number of Bad Pairs asked at Google/Amazon/Meta?
What data structure is used in Count Number of Bad Pairs?
What is the time complexity of Count Number of Bad Pairs?
Ready to solve this problem?
Practice Count Number of Bad Pairs with our built-in code editor and test cases.
Practice on FleetCode