Count Nice Pairs in an Array — Medium Problem & Solution

Let rev(x) be the value of x with its decimal digits reversed — rev(123) = 321, rev(120) = 21.

Difficulty: Medium
Topics: Arrays, Math, Hash Table, 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 <= 100000
0 <= nums[i] <= 1000000000

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 rev with string reversal is fine, but be careful that trailing zeros vanish — rev(120) is 21, not 021.
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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue