Watch 10 video solutions for Count Number of Bad Pairs, a medium level problem involving Array, Hash Table, Math. This walkthrough by NeetCodeIO has 10,814 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 109Problem 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 | 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 |