Problem Description

You are given a 0-indexed integer array nums. A pair of indices (i, j) is called a bad pair if it satisfies both conditions:

• i < j
• j - i != nums[j] - nums[i]

Your task is to return the total number of bad pairs in the array nums.

To understand this problem better, let's break down what makes a pair "bad":

• We're looking at pairs of indices where the first index comes before the second (i < j)
• The difference between the indices (j - i) should NOT equal the difference between their corresponding values (nums[j] - nums[i])
• If these differences are not equal, we count it as a bad pair

For example, if we have indices i = 1 and j = 3 with values nums[1] = 5 and nums[3] = 8:

• Index difference: j - i = 3 - 1 = 2
• Value difference: nums[j] - nums[i] = 8 - 5 = 3
• Since 2 ≠ 3, this would be a bad pair

The solution cleverly transforms the condition j - i != nums[j] - nums[i] into i - nums[i] != j - nums[j]. This transformation allows us to use a hash table to efficiently count pairs. For each position, we track how many previous positions have the same value of index - nums[index]. The positions that don't match this pattern with the current position form bad pairs.

Intuition

The key insight comes from recognizing that counting "bad pairs" directly would be inefficient - we'd need to check every possible pair, resulting in O(n²) time complexity. Instead, we can count the "good pairs" and subtract from the total number of pairs.

Let's think about what makes a pair "good". A pair (i, j) where i < j is good when j - i = nums[j] - nums[i]. We can rearrange this equation:

• j - i = nums[j] - nums[i]
• j - nums[j] = i - nums[i]

This transformation is brilliant! It tells us that for a good pair, both indices have the same value when we compute index - nums[index].

Now, instead of checking pairs, we can track a pattern: for each position i, we calculate i - nums[i]. If we've seen this value before at some earlier positions, those positions form good pairs with the current position.

Here's the counting logic:

• When we're at position i, all positions before it (from 0 to i-1) could potentially form pairs with it
• That's a total of i possible pairs
• Among these, the good pairs are those previous positions where index - nums[index] equals i - nums[i]
• So the bad pairs with position i are: i - (count of good pairs)

By maintaining a hash table that counts occurrences of i - nums[i] as we iterate through the array, we can efficiently determine how many good pairs exist for each position, and consequently, how many bad pairs there are.

Learn more about Math patterns.

Solution Approach

Based on our intuition, we implement the solution using equation transformation and a hash table. The core idea is to transform the bad pair condition and use a counter to efficiently track patterns.

Equation Transformation:

We start with the bad pair condition: j - i != nums[j] - nums[i] for i < j.

By rearranging, we get: i - nums[i] != j - nums[j].

This means a pair (i, j) is bad when the values i - nums[i] and j - nums[j] are different.

Implementation Steps:

1. Initialize a Counter: We use a hash table cnt to count occurrences of i - nums[i] values as we iterate through the array.

2. Iterate Through the Array: For each position i with value nums[i]:

   • Calculate the key: key = i - nums[i]
   • Count bad pairs: All previous positions (total of i positions) minus the positions that have the same key value gives us the number of bad pairs ending at position i
   • Add to answer: ans += i - cnt[key]
   • Update counter: Increment cnt[key] by 1 for future iterations

3. Return the Result: The accumulated sum gives us the total number of bad pairs.

Example Walkthrough:

Let's say nums = [4, 1, 3, 3]:

• Position 0: key = 0 - 4 = -4, bad pairs = 0 - 0 = 0, update cnt[-4] = 1
• Position 1: key = 1 - 1 = 0, bad pairs = 1 - 0 = 1, update cnt[0] = 1
• Position 2: key = 2 - 3 = -1, bad pairs = 2 - 0 = 2, update cnt[-1] = 1
• Position 3: key = 3 - 3 = 0, bad pairs = 3 - 1 = 2 (one good pair with position 1), update cnt[0] = 2
• Total bad pairs = 0 + 1 + 2 + 2 = 5

Time and Space Complexity:

• Time: O(n) - single pass through the array
• Space: O(n) - hash table can store at most n different keys

Example Walkthrough

Let's walk through a small example with nums = [1, 2, 5] to illustrate the solution approach.

Step-by-step process:

We'll track i - nums[i] for each position and use a counter to find bad pairs.

Initial state:

• cnt = {} (empty hash table)
• ans = 0 (bad pairs count)

Position 0 (nums[0] = 1):

• Calculate key: 0 - 1 = -1
• Previous positions that could form pairs: 0 (none before this)
• Good pairs with same key (-1): cnt[-1] = 0 (not in counter yet)
• Bad pairs: 0 - 0 = 0
• Update: ans = 0, cnt[-1] = 1

Position 1 (nums[1] = 2):

• Calculate key: 1 - 2 = -1
• Previous positions that could form pairs: 1 (positions 0)
• Good pairs with same key (-1): cnt[-1] = 1 (position 0 has key -1)
• Bad pairs: 1 - 1 = 0
• Update: ans = 0, cnt[-1] = 2

Position 2 (nums[2] = 5):

• Calculate key: 2 - 5 = -3
• Previous positions that could form pairs: 2 (positions 0 and 1)
• Good pairs with same key (-3): cnt[-3] = 0 (not in counter)
• Bad pairs: 2 - 0 = 2
• Update: ans = 2, cnt[-3] = 1

Verification: Let's verify our answer by checking all pairs manually:

• Pair (0,1): i=0, j=1 → j-i = 1, nums[j]-nums[i] = 2-1 = 1 → 1 = 1 (good pair)
• Pair (0,2): i=0, j=2 → j-i = 2, nums[j]-nums[i] = 5-1 = 4 → 2 ≠ 4 (bad pair)
• Pair (1,2): i=1, j=2 → j-i = 1, nums[j]-nums[i] = 5-2 = 3 → 1 ≠ 3 (bad pair)

Result: 2 bad pairs total, which matches our algorithm's output.

The key insight is that positions 0 and 1 both have i - nums[i] = -1, making them a good pair. Position 2 has a different value (-3), so it forms bad pairs with both previous positions.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because the algorithm iterates through the array exactly once using enumerate(nums), and within each iteration, it performs constant-time operations: accessing and updating the Counter dictionary (both cnt[i - x] and cnt[i - x] += 1 are O(1) operations on average), and performing arithmetic operations (i - cnt[i - x]).

The space complexity is O(n), where n is the length of the array nums. This is due to the Counter dictionary cnt which stores key-value pairs. In the worst case, when all values of i - nums[i] are unique for each index i, the dictionary will contain n distinct keys, requiring O(n) space to store them.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in Other Languages

While Python handles large integers automatically, in languages like Java or C++, the calculation of bad pairs can cause integer overflow when dealing with large arrays.

Problem Example:

• Array size n = 100,000
• Worst case: all pairs are bad = n*(n-1)/2 ≈ 5 billion (exceeds 32-bit integer range)

Solution: Use 64-bit integers (long in Java, long long in C++) for the answer variable:

long badPairs = 0;  // Use long instead of int

2. Misunderstanding the Good vs Bad Pair Logic

A common mistake is incorrectly calculating the number of bad pairs at each position. Some might accidentally count good pairs as bad pairs or vice versa.

Problem Example:

# WRONG: This counts good pairs, not bad pairs
bad_pairs += difference_count[current_difference]

Solution: Remember that at position i:

• Total possible pairs with previous elements = i
• Good pairs = difference_count[current_difference]
• Bad pairs = Total - Good = i - difference_count[current_difference]

3. Forgetting to Update the Counter

Failing to update the difference counter after processing each element will lead to incorrect counts for subsequent elements.

Problem Example:

for index, value in enumerate(nums):
    current_difference = index - value
    bad_pairs += index - difference_count[current_difference]
    # MISSING: difference_count[current_difference] += 1

Solution: Always update the counter after calculating bad pairs for the current position:

difference_count[current_difference] += 1

4. Using Wrong Difference Formula

Some might use value - index instead of index - value, which would give incorrect results.

Problem Example:

# WRONG: This reverses the difference
current_difference = value - index  # Should be index - value

Solution: Stick to the transformed equation: use index - nums[index] consistently throughout the solution.

5. Not Handling Edge Cases

While this solution handles them implicitly, not considering edge cases can lead to errors in modified versions.

Edge Cases to Consider:

• Empty array or single element (should return 0)
• All elements form good pairs (minimum bad pairs)
• All elements form bad pairs (maximum bad pairs)
• Negative numbers in the array

Solution: The current implementation handles these naturally, but if modifying the code, ensure:

if len(nums) <= 1:
    return 0  # No pairs possible