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] <= 109In #2364 Count Number of Bad Pairs, we are asked to count index pairs (i, j) where the relationship between indices and values does not satisfy the required condition. A key observation is to first understand what defines a good pair. The problem states that a pair is good when j - i == nums[j] - nums[i]. By rearranging this equation, we get nums[i] - i == nums[j] - j.
This transformation allows us to convert the problem into a frequency counting task. As we iterate through the array, we compute the value nums[i] - i and track how many times it has appeared using a hash table. Each matching value contributes to the count of good pairs.
Once the number of good pairs is known, we can compute the total possible pairs using the formula n * (n - 1) / 2 and subtract the good pairs to obtain the number of bad pairs. This approach efficiently reduces the complexity to O(n) time with O(n) additional space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map with Mathematical Transformation | O(n) | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Would it be easier to count the number of pairs that are not bad pairs?
Notice that (j - i != nums[j] - nums[i]) is the same as (nums[i] - i != nums[j] - j).
Keep a counter of nums[i] - i. To be efficient, use a HashMap.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of counting pairs with mathematical transformations and hash maps are common in FAANG-style interviews. The problem tests understanding of array manipulation, algebraic rearrangement, and frequency counting techniques.
A hash table (or hash map) is the most suitable data structure. It helps track the frequency of the expression nums[i] - i while iterating through the array, allowing constant-time updates and lookups.
The optimal approach uses a mathematical transformation and a hash map. By converting the condition into nums[i] - i == nums[j] - j, we can count matching values efficiently and derive the number of bad pairs from the total pairs.
Transforming the equation simplifies the condition for identifying good pairs. Instead of checking all pair combinations, the rearranged form lets us group indices by the value nums[i] - i and count matches efficiently.