2364. Count Number of Bad Pairs

Time: O(n)

Space: O(n)

Intuition

Count bad pairs (i,j) where j-i != nums[j]-nums[i]. Equivalently: (nums[i]-i) != (nums[j]-j). Count total pairs minus good pairs.

Algorithm

1Transform: key[i] = nums[i] - i. Count freq of each key. Bad pairs = total pairs - sum(C(freq, 2)).

Common Pitfalls

•Good pairs have equal (nums[i]-i). Total pairs = n*(n-1)/2.

2364.cs

// Approach: Total pairs minus good pairs; good pairs share same (nums[i]-i) value, count via HashMap.
// Time: O(n) Space: O(n)

public class Solution
{
    public long CountBadPairs(int[] nums)
    {
        long ans = 0;
        Dictionary<int, int> count = new Dictionary<int, int>();  // (nums[i] - i)

        for (int i = 0; i < nums.Length; ++i)
        {
            int key = nums[i] - i;
            if (!count.ContainsKey(key))
                count[key] = 0;

            ans += i - count[key]++;
        }

        return ans;
    }
}

Was this solution helpful?