Code Implementation

class Solution:
    def countNicePairs(self, nums):
        from collections import defaultdict
        MOD = 10**9 + 7
        
        def rev(x):
            return int(str(x)[::-1])
        
        count = defaultdict(int)
        res = 0
        for num in nums:
            diff = num - rev(num)
            res = (res + count[diff]) % MOD
            count[diff] += 1
        return res
      

class Solution {
public:
    int countNicePairs(vector<int>& nums) {
        const int MOD = 1e9 + 7;
        unordered_map<int, int> count;
        int res = 0;
        for (int num : nums) {
            int revNum = 0, tmp = num;
            while (tmp) {
                revNum = revNum * 10 + tmp % 10;
                tmp /= 10;
            }
            int diff = num - revNum;
            res = (res + count[diff]) % MOD;
            count[diff]++;
        }
        return res;
    }
};
      

class Solution {
    public int countNicePairs(int[] nums) {
        final int MOD = 1000000007;
        Map<Integer, Integer> count = new HashMap<>();
        int res = 0;
        for (int num : nums) {
            int revNum = 0, tmp = num;
            while (tmp > 0) {
                revNum = revNum * 10 + tmp % 10;
                tmp /= 10;
            }
            int diff = num - revNum;
            res = (res + count.getOrDefault(diff, 0)) % MOD;
            count.put(diff, count.getOrDefault(diff, 0) + 1);
        }
        return res;
    }
}
      

var countNicePairs = function(nums) {
    const MOD = 1e9 + 7;
    const count = new Map();
    let res = 0;
    function rev(x) {
        return parseInt(x.toString().split('').reverse().join(''));
    }
    for (let num of nums) {
        let diff = num - rev(num);
        res = (res + (count.get(diff) || 0)) % MOD;
        count.set(diff, (count.get(diff) || 0) + 1);
    }
    return res;
};
      

Problem Description

Given an array of integers nums, a pair of indices (i, j) is considered a nice pair if 0 <= i < j < nums.length and the following condition holds:

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

Here, rev(x) means reversing the digits of integer x (for example, rev(123) = 321).

Your task is to count the total number of nice pairs in the array. Since the answer can be large, return it modulo 10^9 + 7.

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] < 10^9

Thought Process

At first glance, the problem seems to require checking every possible pair of indices (i, j) and verifying if the nice pair condition holds. This would involve two nested loops, leading to a brute-force solution with quadratic time complexity.

However, with constraints up to 10^5 elements, a brute-force approach is too slow. To optimize, we need to look for a mathematical simplification or a way to use data structures (like a hash map) to count pairs efficiently.

Upon closer inspection, the nice pair condition can be rewritten and simplified, which opens up the possibility of grouping and counting pairs based on a derived value.

Solution Approach

Let's break down the steps to find an efficient solution:

1. Simplify the Condition:
   • The condition nums[i] + rev(nums[j]) == nums[j] + rev(nums[i]) can be rearranged as:
   • nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])
   • This means for every pair of indices that have the same value of nums[k] - rev(nums[k]), they form a nice pair.
2. Count Occurrences:
   • For each number in the array, compute diff = num - rev(num).
   • Use a hash map (dictionary) to count how many times each diff value has already occurred.
3. Count Pairs:
   • For each number, the number of nice pairs it forms is equal to the current count of its diff in the hash map.
   • Add this count to the result, and then increment the count for this diff.
4. Modulo Operation:
   • Since the result can be large, take modulo 10^9 + 7 at each step.

This approach ensures that we only need a single pass through the array, and all operations are efficient.

Example Walkthrough

Let's walk through an example with nums = [42, 11, 1, 97].

• Compute diff for each element:
  • 42 - rev(42) = 42 - 24 = 18
  • 11 - rev(11) = 11 - 11 = 0
  • 1 - rev(1) = 1 - 1 = 0
  • 97 - rev(97) = 97 - 79 = 18
• Process the array and keep a count of each diff:
  • First 42: diff=18, count so far: 0, pairs: 0 (add to map)
  • 11: diff=0, count so far: 0, pairs: 0 (add to map)
  • 1: diff=0, count so far: 1, pairs: 1 (increment result to 1)
  • 97: diff=18, count so far: 1, pairs: 1 (increment result to 2)
• Final answer: 2 nice pairs: (11, 1) and (42, 97)

Time and Space Complexity

• Brute-Force Approach:
  • Time Complexity: O(N²), since for each element, we check all others.
  • Space Complexity: O(1), only a counter is needed.
• Optimized Approach:
  • Time Complexity: O(N), as we process each element once and hash map operations are O(1) on average.
  • Space Complexity: O(N), for the hash map storing counts of each diff.

Summary

By recognizing that the nice pair condition reduces to checking for equal values of nums[i] - rev(nums[i]), we can efficiently count pairs using a hash map. This avoids the inefficiency of a brute-force solution and leverages mathematical insight for optimal performance. The solution is elegant because it transforms a seemingly complex pairwise problem into a simple counting problem.