Count Nice Pairs in an Array — Problem & Solution
Count Nice Pairs in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Nice Pairs in an Array is a medium coding problem on arrays, hash table and math, asked in Amazon, Google and Adobe interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Math, Counting
- Asked at: Amazon, Google, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Let rev(x) be the value of x with its decimal digits reversed — rev(123) = 321, rev(120) = 21.
A pair of indices (i, j) with i < j is nice when nums[i] + rev(nums[j]) == nums[j] + rev(nums[i]).
Return the number of nice pairs, modulo 10^9 + 7.
Example 1
Input: nums = [42,11,1,97]
Output: 2
Explanation: The nice pairs are (0,3) and (1,2).
Example 2
Input: nums = [13,10,35,24,76]
Output: 4
Example 3
Input: nums = [1,2,3]
Output: 3
Explanation: Single digits are their own reversals, so every pair is nice.
Constraints
1 <= nums.length <= 1000000 <= nums[i] <= 1000000000
Hints for Count Nice Pairs in an Array
Hint 1
Rearrange the condition: move the
iterms to one side and thejterms to the other.Hint 2
It becomes
nums[i] - rev(nums[i]) == nums[j] - rev(nums[j]).Hint 3
So group by that key and count pairs within each group as you sweep.
How to solve Count Nice Pairs in an Array
The condition couples i and j only through the quantity x - rev(x). Rewriting it that way turns the problem into counting pairs with equal keys, which one pass with a tally solves.
Approach
- For each value compute
key = x - rev(x). - Sweep the array; before inserting the current key, add its existing tally to the answer — those are the earlier indices it pairs with.
- Increment the tally and reduce the running answer modulo
10^9 + 7.
Why it works
a + rev(b) == b + rev(a) rearranges to a - rev(a) == b - rev(b), an equality between two independent quantities. Counting before inserting attributes each pair to its later index exactly once.
Complexity
- Time —
O(n · digits) - Space —
O(n)
Pitfalls
- Computing
revwith string reversal is fine, but be careful that trailing zeros vanish —rev(120)is21, not021. - The pair count can reach about
n²/2, so reduce modulo as you go rather than at the end. - Inserting before counting makes an element pair with itself.
Reference solution
Python
from typing import List
def countNicePairs(nums: List[int]) -> int:
MOD = 1000000007
seen = {}
total = 0
for x in nums:
key = x - int(str(x)[::-1])
total = (total + seen.get(key, 0)) % MOD
seen[key] = seen.get(key, 0) + 1
return totalJava
public static int countNicePairs(int[] nums) {
final int MOD = 1000000007;
Map<Integer, Integer> seen = new HashMap<>();
long total = 0;
for (int x : nums) {
int r = 0, v = x;
while (v > 0) { r = r * 10 + v % 10; v /= 10; }
int key = x - r;
total = (total + seen.getOrDefault(key, 0)) % MOD;
seen.put(key, seen.getOrDefault(key, 0) + 1);
}
return (int) total;
}C++
int countNicePairs(vector<int>& nums) {
const long long MOD = 1000000007LL;
unordered_map<int, int> seen;
long long total = 0;
for (int x : nums) {
int r = 0, v = x;
while (v > 0) { r = r * 10 + v % 10; v /= 10; }
int key = x - r;
total = (total + seen[key]) % MOD;
seen[key]++;
}
return (int) total;
}JavaScript
var countNicePairs = function(nums) {
var MOD = 1000000007;
var rev = function(x) {
var r = 0, v = x;
while (v > 0) { r = r * 10 + (v % 10); v = Math.floor(v / 10); }
return r;
};
var seen = {}, total = 0;
for (var i = 0; i < nums.length; i++) {
var key = String(nums[i] - rev(nums[i]));
if (seen[key] !== undefined) total = (total + seen[key]) % MOD;
seen[key] = (seen[key] === undefined ? 0 : seen[key]) + 1;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets