Count Nice Pairs in an Array - Solution & Explanation
Problem Statement
You are given an array nums that consists of non-negative integers. Let us define rev(x) as the reverse of the non-negative integer x. For example, rev(123) = 321, and rev(120) = 21. A pair of indices (i, j) is nice if it satisfies all of the following conditions:
0 <= i < j < nums.lengthnums[i] + rev(nums[j]) == nums[j] + rev(nums[i])
Return the number of nice pairs of indices. Since that number can be too large, return it modulo 109 + 7.
Example 1:
Input: nums = [42,11,1,97] Output: 2 Explanation: The two pairs are: - (0,3) : 42 + rev(97) = 42 + 79 = 121, 97 + rev(42) = 97 + 24 = 121. - (1,2) : 11 + rev(1) = 11 + 1 = 12, 1 + rev(11) = 1 + 11 = 12.
Example 2:
Input: nums = [13,10,35,24,76] Output: 4
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 109
Approach Overview
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.
Approach 1: Using Difference with Reverse Approach
For a nice pair, nums[i] + rev(nums[j]) = nums[j] + rev(nums[i]) implies nums[i] - rev(nums[i]) = nums[j] - rev(nums[j]). Use this invariant property to compute measurable differences for each index.
Transform each element nums[i] in the array to nums[i] - rev(nums[i]). Count the frequency of each difference to compute the number of pairs (i, j) with this characteristic efficiently.
The solution builds on the idea that the equation nums[i] - rev(nums[i]) == nums[j] - rev(nums[j]) describes a relationship that clearly defines a valid condition for 'nice' index pairs.
Every time a particular difference is encountered, we count how many times it has appeared previously to compute how many pairs can be formed based on past occurrences, thus avoiding a direct double loop and optimizing for time complexity.
Complexity
Time Complexity: O(N), where N is the length of the nums array since we process each number in the array in constant time.
Space Complexity: O(N), for storing the frequencies of differences.
Approach 2: Two-Pointer Approach (Pairwise Check)
Another less efficient, but intuitive approach is to use a two-pointer technique to check each pair (i, j) for the nice pair condition. This approach isn't time optimized for large input sizes but serves to clearly enforce the criteria pairwise and verify the conditions directly.
This method involves going through each pair directly to see if the condition holds. Although easy to think about, it is not suitable for large-sized arrays.
This C implementation uses two nested loops to check each pair of indices. It calculates the reverse of both numbers and compares their sum to find nice pairs.
It's a straightforward approach that leverages direct pairwise comparison, but this results in less efficiency for large inputs. Suitable for educational purposes or small arrays, it helps grasp the mechanics without advanced data structures.
Complexity
Time Complexity: O(N²), where N is the size of the array, due to the pairwise comparison.
Space Complexity: O(1), constant space as no additional data structures are used.
Approach 3: Equation Transformation + Hash Table
For the index pair (i, j), if it satisfies the condition, then we have nums[i] + rev(nums[j]) = nums[j] + rev(nums[i]), which means nums[i] - nums[j] = rev(nums[j]) - rev(nums[i]).
Therefore, we can use nums[i] - rev(nums[i]) as the key of a hash table and count the number of occurrences of each key. Finally, we calculate the combination of values corresponding to each key, add them up, and get the final answer.
Note that we need to perform modulo operation on the answer.
The time complexity is O(n times log M), where n and M are the length of the nums array and the maximum value in the nums array, respectively. The space complexity is O(n).
Code
Python
Java
C++
Go
TypeScript
JavaScript
C#
Approach 4: Default Approach
Code
Python
Java
C++
Go
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Using Difference with Reverse Approach | Time Complexity: O(N), where N is the length of the nums array since we process each number in the array in constant time. Space Complexity: O(N), for storing the frequencies of differences. |
| Two-Pointer Approach (Pairwise Check) | Time Complexity: O(N²), where N is the size of the array, due to the pairwise comparison. Space Complexity: O(1), constant space as no additional data structures are used. |
| Equation Transformation + Hash Table | — |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer / Pairwise Check (Brute Force) | O(n²) | O(1) | Small arrays or when demonstrating the direct definition of a nice pair |
| Difference with Reverse (Hash Map Counting) | O(n) | O(n) | General case and interview settings where linear performance is required |
Video Solution
Count Nice Pairs in an Array | Simple Clean | Important suggestion | AMAZON | Leetcode-1814 • codestorywithMIK • 7,398 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Nice Pairs in an Array easy or hard?
Count Nice Pairs in an Array Python/Java solution
How to solve Count Nice Pairs in an Array in O(n)?
What is the best approach for Count Nice Pairs in an Array?
Is Count Nice Pairs in an Array asked at Google/Amazon/Meta?
What data structure is used in Count Nice Pairs in an Array?
What is the time complexity of Count Nice Pairs in an Array?
Ready to solve this problem?
Practice Count Nice Pairs in an Array with our built-in code editor and test cases.
Practice on FleetCode