Count Number of Bad Pairs
MedPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward approach is to check every possible pair of indices (i, j) where i < j. For each pair, we directly evaluate the condition j - i != nums[j] - nums[i]. If the condition holds true, we increment a counter for bad pairs.
Algorithm
- Initialize a counter
badPairsCountto 0. - Get the length of the array,
n. - Use a nested loop:
- The outer loop iterates
ifrom0ton-2. - The inner loop iterates
jfromi+1ton-1.
- The outer loop iterates
- Inside the inner loop, check the condition:
if (j - i != nums[j] - nums[i]). - If the condition is true, increment
badPairsCount. - After the loops complete, return
badPairsCount.
Walkthrough
This method uses a nested loop structure to generate all unique pairs of indices (i, j) with i < j. The outer loop runs from i = 0 to n-2, and the inner loop runs from j = i + 1 to n-1. Inside the inner loop, we perform the check j - i != nums[j] - nums[i]. A running counter, initialized to zero, is incremented each time we find such a 'bad pair'. The final value of this counter is the result. Note that the count can exceed the capacity of a 32-bit integer, so a long should be used for the counter.
class Solution { public long countBadPairs(int[] nums) { long badPairsCount = 0; int n = nums.length; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // The condition for a bad pair if ((long)j - i != (long)nums[j] - nums[i]) { badPairsCount++; } } } return badPairsCount; }}Complexity
Time
O(n^2), where n is the number of elements in `nums`. We use nested loops to check every possible pair `(i, j)` with `i < j`, which amounts to `n * (n - 1) / 2` checks.
Space
O(1), as we only use a constant amount of extra space for loop variables and the counter.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space.
Cons
Highly inefficient for the given constraints (n <= 10^5), leading to a Time Limit Exceeded (TLE) error on most platforms.
Solutions
Solution
class Solution {public long countBadPairs(int[] nums) { Map<Integer, Integer> cnt = new HashMap<>(); long ans = 0; for (int i = 0; i < nums.length; ++i) { int x = i - nums[i]; ans += i - cnt.getOrDefault(x, 0); cnt.merge(x, 1, Integer : : sum); } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.