Count number of bad pairs

func countBadPairs(nums []int) int64 {
    hash := make(map[int]int)
    counter := 0
    
    for i, num := range nums {
        diff := num - i
        counter += i - hash[diff]
        hash[diff]++
    }
    
    return int64(counter)
}

Time Complexity O(N)

Space Complexity O(N)

Explanation

In this post, we'll explore an efficient solution to the problem of counting bad pairs in an integer array. A pair of indices (i, j) is considered a bad pair if:

i < j, and
nums[j] - nums[i] ≠ j - i

A brute-force solution that checks every possible pair would run in O(n²) time, which isn't feasible for large arrays. Instead, we can solve the problem in O(n) time by cleverly transforming the condition and using a frequency map.

The Key Observation

Notice that the condition for a pair not to be bad (i.e., a good pair) is: nums[j] - nums[i] = j - i

This can be rearranged into: nums[j] - nums[i] = j - i

In other words, two indices i and j form a good pair if they share the same value of nums[k] - k. With this insight, we can count the number of good pairs, and by extension, deduce the number of bad pairs.

For each index i, the total number of pairs that can be formed with previous indices is i. If hash[diff] (where diff = nums[i] - i) is the number of previous indices with the same difference, then hash[diff] represents the count of good pairs ending at i. Consequently, the number of bad pairs formed with index i is:

bad_pairs = i - hash[diff]

Step-by-Step Explanation

Initialize a Frequency Map
We use a map (hash) to count how many times each value of nums[i] - i has been encountered.
Iterate Over the Array
For each index i and its corresponding value num, calculate the difference:

diff := num - i
Count Bad Pairs at Each Step
- Each new index i forms i pairs with all previous indices.
- Among these, the number of good pairs is exactly the count of previous indices where nums[k] - k == diff (i.e., hash[diff]).
- Hence, the number of bad pairs contributed by the current index is:
  
  counter += i - hash[diff]
Update the Map
After processing the current index, increment the count for the current difference:

hash[diff]++
Return the Result
Finally, cast the counter to an int64 and return it.

Complexity Analysis

Time Complexity:
The function processes the array in a single pass, performing constant-time operations (map lookups and updates) for each element. Thus, the overall time complexity is O(n).
Space Complexity:
The frequency map stores counts for each unique difference (nums[i] - i). In the worst case, where every element results in a unique difference, the space complexity is O(n).