LeetCode 2364 - Count Number of Bad Pairs

The problem asks us to count the number of bad pairs in an array. We are given a 0-indexed integer array nums, and a pair of indices (i, j) is considered bad if: - i < j - j - i !

leetcodemediumarrayhash-tablemathcounting

LeetCode Problem 2364

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Counting

Solution

Problem Understanding

The problem asks us to count the number of bad pairs in an array. We are given a 0-indexed integer array nums, and a pair of indices (i, j) is considered bad if:

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

In other words, for every pair of indices where the first index comes before the second, we need to determine whether the difference between the indices is not equal to the difference between the values at those indices.

At first glance, this sounds like a straightforward pair comparison problem. Since every possible pair (i, j) with i < j could potentially be bad, a naive interpretation might suggest checking every pair individually. However, the input size makes this impractical.

The input is an integer array nums, where:

  • nums.length can be as large as 10^5
  • Each value nums[i] can be as large as 10^9

The output is a single integer representing the total number of bad pairs in the array.

The constraint nums.length <= 10^5 is particularly important. Since the total number of pairs in an array of size n is approximately n² / 2, a brute force solution with quadratic complexity would perform roughly 5 × 10^9 comparisons in the worst case, which is far too slow for LeetCode time limits.

An important observation is that the problem defines bad pairs, but sometimes it is easier to count the opposite, good pairs, and derive the answer indirectly.

A pair (i, j) is good if:

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

Rearranging this equation:

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

This transformation is the key insight that enables an efficient solution.

Several edge cases are worth considering upfront. Arrays with only one element contain no pairs at all, so the answer must be 0. Arrays where all transformed values i - nums[i] are identical produce no bad pairs because every pair becomes good. Arrays with entirely distinct transformed values create the maximum number of bad pairs. Large input sizes also require attention to integer overflow in languages like Go, since the total number of pairs can exceed the range of a 32-bit integer.

Approaches

Brute Force Approach

The most direct approach is to examine every possible pair (i, j) where i < j.

For each pair, we compute:

j - i

and compare it with:

nums[j] - nums[i]

If the two values are different, we increment our bad pair counter.

This method is guaranteed to be correct because it explicitly evaluates the condition for every valid pair. No pair is skipped, and the problem definition is followed exactly.

However, the issue is performance. Since there are O(n²) possible pairs, the algorithm becomes prohibitively slow for n = 10^5.

Optimal Approach, Counting Good Pairs with a Hash Map

Instead of directly counting bad pairs, we count good pairs.

Starting from the condition for a good pair:

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

We rearrange it:

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

This tells us that two indices form a good pair if they share the same value of:

index - nums[index]

Now the problem becomes much simpler. As we iterate through the array, we compute:

key = i - nums[i]

We maintain a hash map storing how many times each key has appeared.

For the current index:

  • If the same key has appeared k times before, then the current index forms k new good pairs.
  • We add this count to the total good pairs.
  • Then we update the frequency of the current key.

Finally:

bad_pairs = total_pairs - good_pairs

where:

total_pairs = n * (n - 1) / 2

This reduces the complexity from quadratic to linear time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Checks every pair individually
Optimal O(n) O(n) Uses hash map to count matching transformed values

Algorithm Walkthrough

  1. Compute the total number of possible pairs.

Since every pair must satisfy i < j, the total number of pairs in an array of length n is:

n × (n - 1) / 2

We will later subtract good pairs from this total. 2. Create a hash map to track frequencies of transformed values.

We use a hash map where:

key = i - nums[i]

and the value is the number of times this key has appeared so far. 3. Iterate through the array from left to right.

At each index i, compute:

current_key = i - nums[i]
  1. Count new good pairs.

If current_key already exists in the hash map, every previous occurrence forms a good pair with the current index.

For example, if the key has appeared 3 times already, then the current index contributes 3 new good pairs. 5. Update the frequency map.

After counting good pairs, increment the frequency of the current key so future indices can match against it. 6. Compute bad pairs.

Once iteration finishes:

bad_pairs = total_pairs - good_pairs

Return the result.

Why it works

The correctness comes from the transformed equation:

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

which simplifies to:

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

This means a pair is good if and only if both indices share the same transformed value. The hash map guarantees that every prior matching index is counted exactly once, so all good pairs are counted correctly. Since every pair is either good or bad, subtracting good pairs from the total gives the exact number of bad pairs.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        n = len(nums)
        total_pairs = n * (n - 1) // 2

        frequency = defaultdict(int)
        good_pairs = 0

        for index, value in enumerate(nums):
            key = index - value

            good_pairs += frequency[key]
            frequency[key] += 1

        return total_pairs - good_pairs

The implementation begins by computing the total number of possible pairs using the combinatorial formula:

n × (n - 1) / 2

We then initialize a hash map called frequency, which tracks how many times each transformed value index - value has appeared.

As we iterate through the array using enumerate, we calculate the key for the current position. If this key already exists in the hash map, then all previous occurrences form good pairs with the current element. We add this count to good_pairs.

After counting matches, we increment the frequency for the current key so future elements can pair with it.

Finally, since every pair is either good or bad, we subtract the number of good pairs from the total number of pairs and return the result.

Go Solution

func countBadPairs(nums []int) int64 {
	n := len(nums)
	totalPairs := int64(n*(n-1)) / 2

	frequency := make(map[int]int64)
	var goodPairs int64 = 0

	for index, value := range nums {
		key := index - value

		goodPairs += frequency[key]
		frequency[key]++
	}

	return totalPairs - goodPairs
}

The Go implementation follows the exact same logic as the Python version, but there are a few language specific details worth noting.

Since the number of pairs can exceed the range of a 32-bit integer, we use int64 for totalPairs, goodPairs, and hash map frequencies. Without this, overflow could occur for large inputs.

Go maps return the zero value automatically when a key does not exist, which means frequency[key] safely returns 0 without requiring an existence check.

Slices in Go naturally handle empty or single-element inputs, so no special case handling is required.

Worked Examples

Example 1

Input:

nums = [4,1,3,3]

First compute total pairs:

n = 4
total_pairs = 4 × 3 / 2 = 6

We now count good pairs.

Index Value Key = i - nums[i] Existing Count Good Pairs Added Frequency Map
0 4 -4 0 0 {-4: 1}
1 1 0 0 0 {-4: 1, 0: 1}
2 3 -1 0 0 {-4: 1, 0: 1, -1: 1}
3 3 0 1 1 {-4: 1, 0: 2, -1: 1}

Total good pairs:

1

Bad pairs:

6 - 1 = 5

Output:

5

Example 2

Input:

nums = [1,2,3,4,5]

Total pairs:

5 × 4 / 2 = 10
Index Value Key = i - nums[i] Existing Count Good Pairs Added Frequency Map
0 1 -1 0 0 {-1: 1}
1 2 -1 1 1 {-1: 2}
2 3 -1 2 2 {-1: 3}
3 4 -1 3 3 {-1: 4}
4 5 -1 4 4 {-1: 5}

Total good pairs:

10

Bad pairs:

10 - 10 = 0

Output:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n) We process each element once, and hash map operations are O(1) on average
Space O(n) In the worst case, every transformed value is unique

The algorithm performs a single pass through the array. Each iteration performs constant time work, consisting mainly of hash map lookups and updates. Because the hash map may store up to n distinct transformed values, the space complexity is linear.

Test Cases

solution = Solution()

assert solution.countBadPairs([4, 1, 3, 3]) == 5  # Example 1
assert solution.countBadPairs([1, 2, 3, 4, 5]) == 0  # Example 2

assert solution.countBadPairs([10]) == 0  # Single element, no pairs
assert solution.countBadPairs([1, 1]) == 1  # One bad pair
assert solution.countBadPairs([1, 2]) == 0  # One good pair

assert solution.countBadPairs([5, 5, 5, 5]) == 6  # All transformed values differ
assert solution.countBadPairs([1, 2, 3, 4]) == 0  # All pairs are good

assert solution.countBadPairs([2, 1, 3]) == 2  # Mixed good and bad pairs
assert solution.countBadPairs([1000000000] * 5) == 10  # Large values

large_input = list(range(1, 100001))
assert solution.countBadPairs(large_input) == 0  # Stress test, all good pairs
Test Why
[4,1,3,3] Validates the first example
[1,2,3,4,5] Validates the second example
[10] Smallest valid input
[1,1] Single bad pair
[1,2] Single good pair
[5,5,5,5] All pairs are bad
[1,2,3,4] Every pair is good
[2,1,3] Mixed scenario
[1000000000] * 5 Large values in input
range(1,100001) Maximum scale stress test

Edge Cases

A single element array is an important edge case because no valid pair (i, j) exists when n = 1. A careless implementation might accidentally perform invalid calculations or return an incorrect nonzero result. This implementation handles it naturally because:

n × (n - 1) / 2

becomes 0, and the loop produces no good pairs.

Arrays where all pairs are good are another important scenario. For example:

[1,2,3,4,5]

Every index produces the same transformed value:

i - nums[i] = -1

This means every possible pair is good, so the number of bad pairs should be 0. The hash map correctly accumulates all matching keys and subtracts them from the total.

Arrays where every pair is bad can also expose bugs. Consider:

[5,5,5,5]

Each transformed value is unique:

-5, -4, -3, -2

Since no transformed value repeats, there are no good pairs. The implementation correctly leaves good_pairs = 0, making the answer equal to the total number of possible pairs.

Finally, very large inputs are important because the number of possible pairs grows quadratically. For n = 100000, the number of pairs is close to 5 × 10^9, which exceeds 32-bit integer limits. The Go implementation avoids overflow by using int64, ensuring correctness for maximum constraint sizes.