Count Nice Pairs in an Array

Medium
673.

Count Nice Pairs in an Array

Count Nice Pairs in an Array is a medium coding problem on arrays, hash table and math, asked in Amazon, Google and Adobe interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var countNicePairs = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

Hints for Count Nice Pairs in an Array

  1. Hint 1

    Rearrange the condition: move the i terms to one side and the j terms to the other.

  2. Hint 2

    It becomes nums[i] - rev(nums[i]) == nums[j] - rev(nums[j]).

  3. 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

  1. For each value compute key = x - rev(x).
  2. Sweep the array; before inserting the current key, add its existing tally to the answer — those are the earlier indices it pairs with.
  3. 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

Java

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