LeetCode 1814 - Count Nice Pairs in an Array

LeetCode Problem 1814

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Counting

Solution

Problem Understanding

The problem gives us an array of non-negative integers called nums. We need to count how many index pairs (i, j) satisfy the following conditions:

• i < j
• nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])

Here, rev(x) means reversing the digits of the integer. For example:

• rev(123) = 321
• rev(120) = 21

The goal is to return the total number of such "nice pairs". Since the number of pairs can become very large, we return the answer modulo 10^9 + 7.

The input size is important:

• nums.length can be as large as 100000
• Each number can be up to 10^9

These constraints immediately tell us that an O(n^2) solution will be too slow. A quadratic solution would require checking roughly 10^10 pairs in the worst case, which is infeasible.

To solve the problem efficiently, we need to transform the equation into a form that allows fast grouping or counting.

There are several important edge cases to keep in mind:

• Arrays containing only one element should return 0, because no pair exists.
• Numbers ending with zeros are important because reversing removes leading zeros. For example, 120 becomes 21.
• Large arrays with many repeated transformed values can generate a very large number of pairs, so modular arithmetic is necessary.
• Values can be 0, and rev(0) is still 0.

Approaches

Brute Force Approach

The most straightforward solution is to check every possible pair (i, j).

For each pair:

1. Compute rev(nums[i])
2. Compute rev(nums[j])
3. Check whether

nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])

If the condition is true, increment the answer.

This approach is correct because it directly evaluates the exact condition from the problem statement for every possible pair.

However, the time complexity is too high. There are O(n^2) pairs, and with n = 100000, this becomes far too slow.

Key Insight for the Optimal Solution

We start from the condition:

nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])

Rearranging terms:

nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])

This transformation is the key observation.

Instead of comparing pairs directly, we compute the value:

value = num - rev(num)

for every number.

Now the problem becomes:

Count how many pairs have the same transformed value.

This is a classic hash map counting problem.

As we iterate through the array:

• If we have already seen the same transformed value k times,
• Then the current element forms k new nice pairs.

This allows us to count pairs in linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every pair directly
Optimal	O(n)	O(n)	Uses hash map grouping by num - rev(num)

Algorithm Walkthrough

1. Create a helper function to reverse an integer.

This function repeatedly extracts digits using modulo % 10 and constructs the reversed number. 2. Initialize a hash map called difference_count.

The key will be:

num - rev(num)

The value will be how many times this transformed value has appeared so far. 3. Initialize the answer variable result = 0. 4. Iterate through each number in nums. 5. For the current number:

• Compute its reverse.
• Compute the transformed difference:

difference = num - rev(num)

6. Check how many times this difference has already appeared.

If the same difference has appeared k times before, then the current number forms k new nice pairs with those earlier elements. 7. Add k to the answer. 8. Update the hash map count for this difference. 9. Apply modulo 10^9 + 7 after each addition to avoid overflow. 10. After processing all numbers, return the result.

Why it works

The algorithm works because the original equation can be algebraically transformed into:

nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])

This means two indices form a nice pair if and only if their transformed values are equal.

The hash map stores how many previous elements had the same transformed value. Every time we encounter another identical value, we can immediately count all newly formed pairs.

Since every pair is counted exactly once when processing the later index, the final answer is correct.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def countNicePairs(self, nums: List[int]) -> int:
        MOD = 10**9 + 7

        def reverse_number(value: int) -> int:
            reversed_value = 0

            while value > 0:
                reversed_value = reversed_value * 10 + value % 10
                value //= 10

            return reversed_value

        difference_count = defaultdict(int)
        result = 0

        for num in nums:
            difference = num - reverse_number(num)

            result = (result + difference_count[difference]) % MOD

            difference_count[difference] += 1

        return result

The implementation follows the exact algorithm described earlier.

The reverse_number helper function reverses digits mathematically without converting to a string. This keeps the implementation efficient and straightforward.

The difference_count hash map tracks how many times each transformed value has appeared.

For each number:

• We compute num - reverse(num)
• We add the current frequency of that difference to the answer
• Then we increment the frequency

This ordering is important. We must count previous occurrences before adding the current one, otherwise we would incorrectly count a number pairing with itself.

The modulo operation is applied during accumulation to ensure the result never grows too large.

Go Solution

func countNicePairs(nums []int) int {
    const MOD int = 1e9 + 7

    reverseNumber := func(value int) int {
        reversed := 0

        for value > 0 {
            reversed = reversed*10 + value%10
            value /= 10
        }

        return reversed
    }

    differenceCount := make(map[int]int)
    result := 0

    for _, num := range nums {
        difference := num - reverseNumber(num)

        result = (result + differenceCount[difference]) % MOD

        differenceCount[difference]++
    }

    return result
}

The Go implementation mirrors the Python logic closely.

A map[int]int is used instead of Python's defaultdict. In Go, reading a missing key from a map automatically returns the zero value, which is convenient for frequency counting.

Integer overflow is not an issue here because we continuously apply modulo arithmetic. The final answer always remains within bounds.

The reverse function uses integer arithmetic rather than string conversion, just like the Python version.

Worked Examples

Example 1

Input:

nums = [42,11,1,97]

First compute transformed values:

Number	Reverse	Difference
42	24	18
11	11	0
1	1	0
97	79	18

Now trace the algorithm:

Step	Number	Difference	Existing Count	New Pairs Added	Result	Hash Map State
1	42	18	0	0	0	{18:1}
2	11	0	0	0	0	{18:1, 0:1}
3	1	0	1	1	1	{18:1, 0:2}
4	97	18	1	1	2	{18:2, 0:2}

Final answer:

2

Example 2

Input:

nums = [13,10,35,24,76]

Compute transformed values:

Number	Reverse	Difference
13	31	-18
10	1	9
35	53	-18
24	42	-18
76	67	9

Trace execution:

Step	Number	Difference	Existing Count	New Pairs Added	Result
1	13	-18	0	0	0
2	10	9	0	0	0
3	35	-18	1	1	1
4	24	-18	2	2	3
5	76	9	1	1	4

Final answer:

4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each number is processed once
Space	O(n)	Hash map may store up to n distinct differences

The reverse operation itself takes at most O(log10(num)) time, because it processes digits one by one. Since each number has at most 10 digits, this cost is effectively constant.

Therefore, the overall runtime remains linear relative to the array size.

The hash map can grow to contain one entry per element in the worst case, so the space complexity is O(n).

Test Cases

solution = Solution()

# Provided examples
assert solution.countNicePairs([42, 11, 1, 97]) == 2  # Example 1
assert solution.countNicePairs([13, 10, 35, 24, 76]) == 4  # Example 2

# Single element
assert solution.countNicePairs([5]) == 0  # No possible pairs

# All numbers produce same difference
assert solution.countNicePairs([11, 22, 33]) == 3  # 3 choose 2

# Numbers with trailing zeros
assert solution.countNicePairs([10, 100, 1000]) == 3  # All differences match

# No nice pairs
assert solution.countNicePairs([1, 2, 3, 4]) == 6  # All single digits reverse to themselves

# Mixed values
assert solution.countNicePairs([42, 24]) == 0  # Different differences

# Zeros
assert solution.countNicePairs([0, 0, 0]) == 3  # All identical

# Large repeated group
assert solution.countNicePairs([1] * 1000) == 499500  # Large combinational count

# Different transformed values
assert solution.countNicePairs([12, 21, 34, 43]) == 2  # Two matching groups

# Large numbers
assert solution.countNicePairs([1000000000, 1]) == 0  # Large input values

Test Case Summary

Test	Why
[42,11,1,97]	Validates first official example
[13,10,35,24,76]	Validates second official example
[5]	Tests minimum array size
[11,22,33]	Tests all-pairs scenario
[10,100,1000]	Tests reversing numbers with trailing zeros
[1,2,3,4]	Tests single-digit behavior
[42,24]	Tests absence of valid pairs
[0,0,0]	Tests handling of zeros
[1] * 1000	Stress test for large pair counts
[12,21,34,43]	Tests multiple independent groups
[1000000000,1]	Tests very large numbers

Edge Cases

One important edge case involves numbers with trailing zeros, such as 10, 100, or 1200. When reversed, leading zeros disappear automatically. For example, 120 becomes 21, not 021. A careless implementation using strings might mishandle this transformation. The provided implementation avoids this issue by using mathematical digit extraction.

Another important case is arrays where all transformed values are identical. For example:

[11, 22, 33]

Each number has difference 0, so every pair is nice. The number of pairs grows combinatorially, which can become very large for big arrays. The implementation correctly handles this using incremental counting and modulo arithmetic.

Arrays containing zeros are also important. Since rev(0) = 0, the transformed difference remains 0. Multiple zeros therefore all form nice pairs with each other. The reverse function correctly handles 0 because the loop never executes and returns 0.

A subtle edge case is arrays with only one element. Since the condition requires i < j, no pairs are possible. The algorithm naturally handles this because the loop never finds any prior matching differences.

Finally, very large input sizes require an efficient solution. The optimal algorithm processes each number once and uses a hash map for constant average-time lookups, ensuring it remains efficient even for arrays of size 100000.