Count Nice Pairs in an Array

Count Nice Pairs in an Array

What is this problem about?

A "nice pair" in an array is defined as a pair of indices $(i, j)$ such that $i < j$ and $nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])$, where $rev(x)$ is the reverse of the integer $x$. The goal is to count the total number of such pairs in the given array and return the result modulo $10^9 + 7$.

Why is this asked in interviews?

Companies like Uber and Amazon ask this to test your ability to simplify mathematical equations. At first glance, it looks like an $O(n^2)$ problem. However, the condition can be rewritten as $nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])$. This transformation is a high-signal indicator that a candidate can optimize a search problem using hashing.

Algorithmic pattern used

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

1. Define a transformation function: $f(x) = x - rev(x)$.
2. Calculate $f(nums[i])$ for every element in the array.
3. Use a Hash Map to store the frequency of each transformed value.
4. For each value with frequency $c$, the number of nice pairs is $\binom{c}{2} = \frac{c imes (c-1)}{2}$.

Example explanation

Array: [13, 10, 35, 24]

• $f(13) = 13 - 31 = -18$
• $f(10) = 10 - 01 = 9$
• $f(35) = 35 - 53 = -18$
• $f(24) = 24 - 42 = -18$
• Frequency Map: {-18: 3, 9: 1}.
• For -18: $\frac{3 imes 2}{2} = 3$ pairs.
• For 9: $\frac{1 imes 0}{2} = 0$ pairs. Total: 3 nice pairs.

Common mistakes candidates make

One common mistake is trying to iterate through all pairs $(i, j)$, which is too slow. Another is not handling the modulo arithmetic correctly, especially during the summation phase. Some candidates also forget that $rev(10)$ is $1$, not $01$, although the mathematical result remains consistent if treated as an integer.

Interview preparation tip

When you see an equality condition involving two independent variables like $g(i, j) = h(i, j)$, try to move all $i$ terms to one side and all $j$ terms to the other. If you can reach $F(i) = F(j)$, you can solve the problem in linear time using a Hash Map.