Count Number of Bad Pairs

Count Number of Bad Pairs

What is this problem about?

In an array nums, a pair of indices $(i, j)$ is called a "bad pair" if $i < j$ and $j - i eq nums[j] - nums[i]$. You need to find the total number of bad pairs in the array. This problem is about calculating the complement: it's often easier to count "good pairs" and subtract them from the total number of possible pairs.

Why is this asked in interviews?

Companies like Microsoft and Google use this problem to see if a candidate can recognize mathematical patterns and optimize a quadratic brute-force approach. The condition for a "good pair" is $j - i == nums[j] - nums[i]$, which can be rearranged to $nums[i] - i == nums[j] - j$. This simple algebraic shift allows the problem to be solved using a frequency map in linear time.

Algorithmic pattern used

The pattern used is Mathematical Rearrangement and Complementary Counting with a Hash Table.

1. Total pairs in an array of size $n$ is $\binom{n}{2} = \frac{n imes (n-1)}{2}$.
2. A pair is "good" if $nums[i] - i == nums[j] - j$.
3. Use a Hash Map to count how many times each value of $(nums[i] - i)$ appears.
4. Total bad pairs = Total pairs - Good pairs.

Example explanation

Array: [4, 1, 3, 3]

• Index 0: $4 - 0 = 4$
• Index 1: $1 - 1 = 0$
• Index 2: $3 - 2 = 1$
• Index 3: $3 - 3 = 0$
• Transformed values: [4, 0, 1, 0].
• Map: {4: 1, 0: 2, 1: 1}.
• Good pairs: Only the two 0s can form a pair. $\binom{2}{2} = 1$.
• Total pairs: $\binom{4}{2} = 6$.
• Bad pairs: $6 - 1 = 5$.

Common mistakes candidates make

The most common mistake is attempting to check all pairs using a nested loop, which is $O(n^2)$ and will time out for large arrays. Another mistake is forgetting to use 64-bit integers (long) for the counts, as the number of pairs can grow very large ($10^{10}$ for $n=10^5$).

Interview preparation tip

Always look for the "total minus something" strategy when counting "bad" or "invalid" items. If the condition for being "bad" is complex, check if the condition for being "good" is simpler to calculate using a Hash Map.