2364. Count Number of Bad Pairs - Detailed Explanation

Problem Statement

You are given a 0-indexed integer array nums. We define a pair of indices (i, j) to be a bad pair if i < j and j - i != nums[j] - nums[i]. In other words, the difference between the indices is not equal to the difference between the corresponding values. The task is to count the total number of bad pairs in the array.

Example 1:

• Input: nums = [4, 1, 3, 3]
• Output: 5
• Explanation: There are 6 possible pairs of indices (i, j) with i < j for this array. Out of these, 5 pairs are bad:
  • (0, 1) is a bad pair because 1 - 0 ≠ 1 - 4 (i.e., index difference 1 vs value difference -3).
  • (0, 2) is a bad pair because 2 - 0 ≠ 3 - 4 (2 vs -1).
  • (0, 3) is a bad pair because 3 - 0 ≠ 3 - 4 (3 vs -1).
  • (1, 2) is a bad pair because 2 - 1 ≠ 3 - 1 (1 vs 2).
  • (2, 3) is a bad pair because 3 - 2 ≠ 3 - 3 (1 vs 0).
    Only one pair (which is (1, 3)) is not a bad pair in this case. Therefore, the total number of bad pairs is 5.

Example 2:

• Input: nums = [1, 2, 3, 4, 5]
• Output: 0
• Explanation: There are no bad pairs because for every pair (i, j), the condition j - i = nums[j] - nums[i] holds. The array is strictly increasing by 1 at each step, so the difference in indices equals the difference in values for any pair. Hence, all pairs are "good" and the count of bad pairs is 0.

Example 3:

• Input: nums = [2, 2, 2]
• Output: 3
• Explanation: The array has 3 elements, so there are 3 possible pairs: (0,1), (0,2), and (1,2). All of these pairs turn out to be bad. For instance, for pair (0,1), we have 1 - 0 = 1 but 2 - 2 = 0 for the values, which do not match. Similarly, every pair of distinct indices has index difference 1 or 2, while the value differences are 0 (because all values are equal). Thus, all 3 pairs are bad.

Constraints:

• 1 <= nums.length <= 100,000
• 1 <= nums[i] <= 1,000,000,000

The result can be large (in the order of tens of billions for the largest arrays), so make sure to use a data type (like 64-bit integer) that can handle large counts.

Hints

• Hint 1: Try to understand the condition for a "bad pair." If a pair is not bad (i.e., a "good" pair), it satisfies j - i = nums[j] - nums[i]. See if this equation can be rearranged or transformed into a simpler form. This might reveal a pattern or a property that you can exploit.

• Hint 2: Think about the total number of pairs possible in an array of length n. If you can efficiently count how many pairs are good, you can subtract that from the total to get the number of bad pairs. Counting good pairs might be easier if you find a suitable way to categorize or group indices that form good pairs.

• Hint 3: Consider using a data structure like a hash map (dictionary) to count occurrences of a certain value related to each index. The equation from Hint 1 can guide you on what value to use. By counting these occurrences, you can determine how many pairs share that property (hence, are good pairs). Avoid brute force comparisons for each pair since that would be too slow for large inputs.

Multiple Approaches

Brute Force Approach

A straightforward way to solve the problem is to check every possible pair of indices and count those that satisfy the "bad pair" condition. This means using two nested loops: the outer loop goes through each index i, and the inner loop checks every index j > i. For each pair (i, j), we verify if j - i is not equal to nums[j] - nums[i]. If they are not equal, we increment a bad pair counter.

Step-by-step (Brute Force):

1. Initialize a counter bad_count = 0.
2. Loop i from 0 to n-1 (where n is the length of nums).
3. For each i, loop j from i+1 to n-1.
4. Check the condition: if j - i != nums[j] - nums[i], then this is a bad pair. Increment bad_count.
5. After checking all pairs, bad_count will hold the total number of bad pairs.

Example (Brute Force):
Consider nums = [3, 1, 2]. The array length n = 3, so total pairs to check = 3:

• Pair (0, 1):
  • Index difference = 1 - 0 = 1
  • Value difference = nums[1] - nums[0] = 1 - 3 = -2
  • These are not equal (1 ≠ -2), so this is a bad pair.
• Pair (0, 2):
  • Index difference = 2 - 0 = 2
  • Value difference = nums[2] - nums[0] = 2 - 3 = -1
  • 2 ≠ -1, so this is a bad pair.
• Pair (1, 2):
  • Index difference = 2 - 1 = 1
  • Value difference = nums[2] - nums[1] = 2 - 1 = 1
  • 1 = 1, so this pair is not bad (it's a good pair).

Out of these, 2 pairs are bad. The brute force approach would correctly count bad_count = 2 for this example.

Analysis of Brute Force: This approach is easy to understand, but it is extremely inefficient for large arrays. It checks every pair of indices, resulting in \mathcal{O}(n^2) time complexity. For n = 100,000, the number of pairs is on the order of 10^{10}, which is far too many to check one by one. Therefore, the brute force method will time out for large inputs and is not feasible within the problem constraints.

Optimized Approach (Using Math and Hash Map)

To optimize, we need to reduce the pair checking. A key observation comes from analyzing the condition for good pairs (the opposite of bad pairs). A pair (i, j) is good if:

j - i = nums[j] - nums[i].

We can rearrange this equation:

j - i = nums[j] - nums[i]
=> j + nums[i] = i + nums[j]
=> j - nums[j] = i - nums[i]

This rearrangement shows that for a pair to be good, the value of i - nums[i] must be the same for both indices. In other words, if we define a new value for each index k as diff[k] = k - nums[k], then any two indices with the same diff value form a good pair.

Why this works: If diff[i] = diff[j] (meaning i - nums[i] = j - nums[j]), then rearranging gives j - i = nums[j] - nums[i], which is exactly the condition for a good pair. Conversely, if diff[i] is different from diff[j], then j - i will not equal nums[j] - nums[i], meaning (i, j) is a bad pair.

Strategy: Using this insight, we can count good pairs efficiently:

1. Compute diff[i] = i - nums[i] for each index i.

2. Use a hash map (or dictionary) to count how many times each diff value occurs.

3. For each unique diff value with frequency f in the map:

   • The number of good pairs contributed by this diff value is the number of ways to choose 2 indices out of f. This is given by the combination formula C(f, 2) = \frac{f \times (f-1)}{2} (which is 0 if f is less than 2).

4. Sum up the counts of good pairs for all diff values.

5. Calculate total pairs in the array: total pairs = \frac{n \times (n-1)}{2}, where n is the length of nums.

6. Finally, bad pairs = total pairs - good pairs.

This avoids explicitly checking every pair. We group indices by their diff values and count pair combinations within each group.

Step-by-step (Optimized):

• Create an empty hash map freq to count frequencies of diff values.

• Loop through the array indices i = 0 to n-1:

  • Compute diff = i - nums[i].
  • Update freq[diff] += 1 (increment the count for that diff value).

• Initialize good_count = 0.

• For each entry (value, count) in freq:

  • If count is at least 2, add \frac{count \times (count-1)}{2} to good_count.
  • (If count is 0 or 1, it contributes 0 good pairs.)

• Compute total_pairs = frac\{n \times (n-1)}{2}.

• Compute bad_count = total_pairs - good_count.

• Return or output bad_count.

Example (Optimized):
Revisiting the Example 1 array nums = [4, 1, 3, 3]:

• Calculate diff for each index:
  • Index 0: diff[0] = 0 - 4 = -4
  • Index 1: diff[1] = 1 - 1 = 0
  • Index 2: diff[2] = 2 - 3 = -1
  • Index 3: diff[3] = 3 - 3 = 0
• Frequency map of diff values:
  {-4: 1, 0: 2, -1: 1}
  Here, -4 occurs once, 0 occurs twice, and -1 occurs once.
• Count good pairs from these frequencies:
  • The value -4 with frequency 1 gives 0 good pairs (need at least 2 indices to form a pair).
  • The value 0 with frequency 2 gives C(2, 2) = 1 good pair. (Those two indices with diff = 0 form a good pair; indeed, these are indices 1 and 3, which we saw was the only good pair.)
  • The value -1 with frequency 1 gives 0 good pairs.
  • Total good_count = 1.
• Total pairs in array of length 4: C(4, 2) = \frac{4 \times 3}{2} = 6.
• Bad pairs = total pairs - good pairs = 6 - 1 = 5, which matches the output.

This optimized method computes the answer in a single pass (to build the map) plus a second pass over the map entries, which is much more efficient than checking every pair.

Additional Optimization: Instead of computing total pairs and subtracting, we could directly count bad pairs in one pass. For each index as we iterate, determine how many previous indices do not have the same diff value. For example, at index i, the number of pairs (j, i) (with j < i) that are bad is i (total previous indices) minus the number of previous indices with the same diff as i. We can maintain a running count of seen diff values and accumulate bad pairs on the fly. However, whether you count good pairs or bad pairs first, the efficiency is similar. The main idea is using the hash map to avoid the double loop.

Code Implementations

Python Implementation