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.
A more efficient approach is to count the number of 'good pairs' and subtract this from the total number of pairs. A pair (i, j) is 'good' if i < j and j - i == nums[j] - nums[i]. This condition can be rearranged to nums[i] - i == nums[j] - j. This insight transforms the problem into finding pairs of indices (i, j) that have the same value for the expression nums[k] - k. This can be solved efficiently in a single pass using a hash map to store the frequencies of these values.
Algorithm
- The total number of pairs
(i, j)withi < jistotal_pairs = n * (n - 1) / 2. - The number of bad pairs is
total_pairs - good_pairs. - A pair is 'good' if
j - i == nums[j] - nums[i], which can be rearranged tonums[i] - i == nums[j] - j. - We can count good pairs efficiently:
- Initialize
good_pairs_count = 0and a hash mapfreq_map. - Iterate through the array
numsfromi = 0ton-1. - For each element, calculate
diff = nums[i] - i. - The number of previous elements that form a good pair with the current element is the current frequency of
diffinfreq_map. Add this frequency togood_pairs_count. - Increment the frequency of
diffinfreq_map.
- Initialize
- Finally, return
total_pairs - good_pairs_count.
Walkthrough
First, we recognize that Total Pairs = Good Pairs + Bad Pairs. The total number of pairs (i, j) with i < j in an array of length n is n * (n - 1) / 2. We can find the number of bad pairs by calculating Total Pairs - Good Pairs.
The condition for a good pair, nums[i] - i == nums[j] - j, means we need to count how many pairs of indices have an equal nums[k] - k value. We can do this in one pass. We iterate through the array, and for each element nums[i], we calculate diff = nums[i] - i. We use a hash map to keep track of the frequencies of these diff values encountered so far. For the current i, the number of good pairs it forms with elements at indices j < i is exactly the number of times we have already seen the value diff. We add this count to our goodPairs total and then update the map with the diff from the current element.
import java.util.HashMap;import java.util.Map; class Solution { public long countBadPairs(int[] nums) { int n = nums.length; long goodPairs = 0; // Map to store frequency of (nums[i] - i) Map<Integer, Integer> freq = new HashMap<>(); for (int i = 0; i < n; i++) { int diff = nums[i] - i; // The number of good pairs ending at index i is the number of times // we've seen the same 'diff' value before. goodPairs += freq.getOrDefault(diff, 0); // Increment the frequency of the current 'diff' value. freq.put(diff, freq.getOrDefault(diff, 0) + 1); } // Total number of pairs is n * (n - 1) / 2 long totalPairs = (long)n * (n - 1) / 2; // Bad pairs = Total pairs - Good pairs return totalPairs - goodPairs; }}Complexity
Time
O(n), where n is the number of elements in `nums`. We iterate through the array once, and each hash map operation (get, put) takes O(1) time on average.
Space
O(n) in the worst case. The hash map might need to store up to `n` distinct key-value pairs if all `nums[i] - i` values are unique.
Trade-offs
Pros
Highly efficient with a linear time complexity, making it suitable for large inputs.
Solves the problem in a single pass through the array.
Cons
Requires extra space for the hash map, which can be up to O(n) in the worst case.
The logic is less direct than the brute-force approach due to the mathematical rearrangement of the condition.
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; }}class Solution {public: long long countBadPairs(vector<int> &nums) { unordered_map<int, int> cnt; long long ans = 0; for (int i = 0; i < nums.size(); ++i) { int x = i - nums[i]; ans += i - cnt[x]; ++cnt[x]; } return ans; }};class Solution: def countBadPairs(self, nums: List[int]) -> int: cnt = Counter() ans = 0 for i, x in enumerate(nums): ans += i - cnt[i - x] cnt[i - x] += 1 return ansVideo 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.