Count Nice Pairs in an Array - Solution & Explanation

Problem Overview: You are given an integer array nums. A pair (i, j) is considered nice if nums[i] + rev(nums[j]) == nums[j] + rev(nums[i]), where rev(x) reverses the digits of x. The goal is to count how many such pairs exist with i < j, returning the result modulo 1e9 + 7.

Approach 1: Two-Pointer / Pairwise Check (Brute Force) (O(n²) time, O(1) space)

The most direct approach checks every pair of indices. Use two nested loops: the outer loop selects index i, and the inner loop iterates through j > i. For each pair, compute rev(nums[i]) and rev(nums[j]), then verify whether the equation nums[i] + rev(nums[j]) == nums[j] + rev(nums[i]) holds. This method requires no extra data structures and only constant additional memory. The drawback is the quadratic runtime, which becomes too slow when the array size grows to tens of thousands. Still, it clearly demonstrates the pair relationship and is useful as a baseline solution during interviews.

Approach 2: Difference with Reverse (Hash Map Counting) (O(n) time, O(n) space)

The key observation simplifies the equation. Rearranging nums[i] + rev(nums[j]) == nums[j] + rev(nums[i]) gives nums[i] - rev(nums[i]) == nums[j] - rev(nums[j]). Instead of comparing pairs directly, compute a transformed value diff = num - rev(num) for each element. Two indices form a nice pair if they share the same diff. Use a hash map to track how many times each difference has appeared. While iterating through the array, look up the current diff in the map and add its frequency to the answer because each previous occurrence forms a new pair. Then increment the stored count.

This technique converts a pair comparison problem into a frequency counting problem using a hash table. Each element is processed once, giving O(n) time complexity. The extra space stores counts of differences, which in the worst case grows to O(n). The digit reversal operation is constant time because the number of digits in an integer is bounded.

Conceptually, the algorithm combines ideas from array traversal and frequency counting. Once the algebraic transformation is recognized, the implementation becomes short and efficient.

Recommended for interviews: Start by describing the brute-force pairwise comparison to show you understand the definition of a nice pair. Then derive the transformation num - rev(num) and switch to the hash map counting approach. Interviewers expect the O(n) solution because it demonstrates pattern recognition and the ability to convert pair constraints into a frequency grouping problem.