#1814

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count Nice Pairs in an Array

Count Nice Pairs in an Array requires efficiently pairing numbers where nums[i] + rev(nums[j]) equals nums[j] + rev(nums[i]).

array hash table math counting

Problem Statement

You are given an array of non-negative integers nums. Define rev(x) as the integer obtained by reversing the digits of x. A pair of indices (i, j) is considered nice if i < j and nums[i] + rev(nums[j]) equals nums[j] + rev(nums[i]). Your task is to count all such nice pairs efficiently.

Return the total number of nice pairs modulo 10^9 + 7. Constraints: 1 <= nums.length <= 10^5 and 0 <= nums[i] <= 10^9. For example, nums = [42,11,1,97] produces 2 nice pairs because (0,3) and (1,2) satisfy the condition.

Examples

Example 1

Input: nums = [42,11,1,97]

Output: 2

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

Example details omitted.

Constraints

1 <= nums.length <= 105
0 <= nums[i] <= 109

Solution Approach

Transform the problem using subtraction

Rewrite the nice pair condition as nums[i] - rev(nums[i]) == nums[j] - rev(nums[j]). This converts the problem into counting equal differences, which simplifies scanning and avoids redundant pair checks.

Use a hash map for frequency counting

Iterate through nums and calculate the key as nums[i] - rev(nums[i]). Store the frequency of each key in a hash map. Each time a key repeats, it forms as many new nice pairs as the current count, allowing O(n) accumulation.

Apply modulo arithmetic for large totals

Since the number of nice pairs can be very large, maintain the running total modulo 10^9 + 7. This prevents integer overflow and ensures the result fits the problem constraints.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

Time complexity is O(n) because each element is processed once. Space complexity is O(n) for the hash map storing difference counts.

What Interviewers Usually Probe

Look for an O(n^2) brute force first but quickly pivot to hash-based counting.
Expect candidates to notice the subtraction transformation nums[i] - rev(nums[i]).
Emphasize handling modulo arithmetic correctly to prevent overflow.

Common Pitfalls or Variants

Common pitfalls

Attempting nested loops leads to O(n^2) and timeouts on large arrays.
Forgetting to reverse numbers correctly can produce incorrect counts.
Neglecting modulo 10^9+7 results in integer overflow for large arrays.

Follow-up variants

Count pairs where nums[i] + rev(nums[j]) - nums[j] - rev(nums[i]) equals a target value instead of zero.
Find nice pairs in a subarray or with additional constraints on index distance.
Return the actual index pairs rather than just the count, preserving order.

FAQ

What is the main trick to solve Count Nice Pairs in an Array efficiently?

The key is transforming the condition into nums[i] - rev(nums[i]) == nums[j] - rev(nums[j]) and using a hash map to count frequencies.

Why do we use modulo 10^9+7 in this problem?

The number of nice pairs can be very large, and modulo prevents integer overflow while satisfying problem constraints.

Can we use a nested loop for Count Nice Pairs?

Yes, but nested loops lead to O(n^2) time complexity, which is too slow for arrays of size up to 10^5.

How do you reverse numbers correctly in this context?

Convert the number to a string, reverse the string, then convert back to integer, handling leading zeros appropriately.

Does GhostInterview help with verifying large input arrays?

Yes, it simulates hash-based counting and ensures the modulo arithmetic is applied correctly for large arrays.

terminal

Solution

Solution 1: 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])$.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def countNicePairs(self, nums: List[int]) -> int:
        def rev(x):
            y = 0
            while x:
                y = y * 10 + x % 10
                x //= 10
            return y

        cnt = Counter(x - rev(x) for x in nums)
        mod = 10**9 + 7
        return sum(v * (v - 1) // 2 for v in cnt.values()) % mod

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def countNicePairs(self, nums: List[int]) -> int:
        def rev(x):
            y = 0
            while x:
                y = y * 10 + x % 10
                x //= 10
            return y

        cnt = Counter(x - rev(x) for x in nums)
        mod = 10**9 + 7
        return sum(v * (v - 1) // 2 for v in cnt.values()) % mod

Continue Practicing

#1994 the number of good subsets #2001 number of pairs of interchangeable rectangles #1512 number of good pairs