# Count Nice Pairs in an Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-nice-pairs-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/count-nice-pairs-in-an-array
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
**Companies:** [Block](https://scaleengineer.com/companies/block)
---
## Problem
You are given an array `nums` that consists of non-negative integers. Let us define `rev(x)` as the reverse of the non-negative integer `x`. For example, `rev(123) = 321`, and `rev(120) = 21`. A pair of indices `(i, j)` is **nice** if it satisfies all of the following conditions:

* `0 <= i < j < nums.length`
* `nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])`

Return _the number of nice pairs of indices_. Since that number can be too large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** nums = [42,11,1,97]
**Output:** 2
**Explanation:** 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

**Constraints:**

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

# Approaches
## Brute Force Iteration
This approach directly translates the problem statement into code. It involves checking every possible pair of indices `(i, j)` where `i < j` to see if they form a "nice pair". For each pair, it computes the reverse of the corresponding numbers and verifies if the condition `nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])` holds true.
**Time:** O(N^2 * log(M)), where N is the length of the `nums` array and M is the maximum value in `nums`. The two nested loops result in O(N^2) iterations. Inside each iteration, the `rev()` function is called, which takes logarithmic time proportional to the number of digits in the number M. · **Space:** O(1) extra space, as we only use a few variables to store the count and loop indices.
**Pros:** Simple to understand and implement directly from the problem definition.; Requires minimal extra space.
**Cons:** Extremely inefficient for large inputs due to its quadratic time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error on most competitive programming platforms for the given constraints.
### Explanation
The brute-force method uses two nested loops to generate all unique pairs of indices `(i, j)` such that `0 <= i < j < nums.length`. The outer loop runs from `i = 0` to `n-1`, and the inner loop from `j = i + 1` to `n-1`, where `n` is the length of the array. Inside the inner loop, we first need a helper function `rev(x)` to compute the reverse of an integer. This function can be implemented by repeatedly taking the last digit of the number and building the reversed number. We then check if `nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])`. If the condition is met, we increment a counter. Since the total count can be very large, the counter should be a `long` to avoid overflow. Finally, we return the total count modulo `10^9 + 7`.

```java
class Solution {
    private int rev(int n) {
        int reversed = 0;
        while (n > 0) {
            reversed = reversed * 10 + n % 10;
            n /= 10;
        }
        return reversed;
    }

    public int countNicePairs(int[] nums) {
        int n = nums.length;
        long count = 0;
        int MOD = 1_000_000_007;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((long)nums[i] + rev(nums[j]) == (long)nums[j] + rev(nums[i])) {
                    count++;
                }
            }
        }
        return (int)(count % MOD);
    }
}
```
### Algorithm
1. Initialize a counter `count` to 0.
2. Define the modulo constant `MOD = 1_000_000_007`.
3. Create a helper function `rev(int n)` that returns the reverse of the integer `n`.
4. Use a nested loop structure. The outer loop iterates with index `i` from `0` to `nums.length - 2`.
5. The inner loop iterates with index `j` from `i + 1` to `nums.length - 1`.
6. Inside the inner loop, for each pair `(nums[i], nums[j])`, check if the nice pair condition `nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])` is satisfied.
7. To avoid potential integer overflow during the check, cast the numbers to a `long` before addition.
8. If the condition is true, increment the `count`.
9. After the loops complete, return `count % MOD`.

## Optimized Approach using Hash Map
A more efficient approach is to first transform the condition for a nice pair. The original condition `nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])` can be algebraically rearranged to `nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])`. This insight changes the problem from a two-variable check to a one-variable property. The problem is now equivalent to finding the number of pairs `(i, j)` with `i < j` that have the same value for the expression `x - rev(x)`. We can solve this efficiently by using a hash map to count the frequencies of these difference values.
**Time:** O(N * log(M)), where N is the length of the `nums` array and M is the maximum value in `nums`. We iterate through the array once (O(N)). For each element, we compute `rev()` which takes O(log(M)) time, and perform hash map operations which take O(1) on average. · **Space:** O(N), where N is the number of elements in `nums`. In the worst-case scenario, if every `num - rev(num)` difference is unique, the hash map will store N key-value pairs.
**Pros:** Highly efficient with a linear time complexity relative to the input size.; Passes the time limits for large constraints by avoiding nested loops.; The logic is elegant and based on a clever mathematical transformation of the problem.
**Cons:** Requires extra space to store the frequency map, which can be up to O(N) in the worst case.
### Explanation
The core idea is that if `k` numbers in the array yield the same result for `num - rev(num)`, they can form `k * (k - 1) / 2` nice pairs among themselves. We can calculate this total sum efficiently in a single pass.

We iterate through the `nums` array, and for each number, we calculate `diff = num - rev(num)`. We use a hash map to keep track of how many times we've seen each `diff` value so far. When we process a new number and calculate its `diff`, we look up this `diff` in our map. The count already in the map for this `diff` tells us how many previous numbers can form a nice pair with the current number. We add this count to our total `nicePairs` result. After that, we increment the count for the current `diff` in the map to include the current number for future comparisons.

This way, for a group of `k` numbers with the same `diff`, we add `0` for the first number, `1` for the second, `2` for the third, and so on, up to `k-1` for the k-th number. The sum `0 + 1 + ... + (k-1)` is exactly `k * (k - 1) / 2`.

All additions to the `nicePairs` count must be performed modulo `10^9 + 7` to prevent overflow.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    private int rev(int n) {
        int reversed = 0;
        while (n > 0) {
            reversed = reversed * 10 + n % 10;
            n /= 10;
        }
        return reversed;
    }

    public int countNicePairs(int[] nums) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        int nicePairs = 0;
        int MOD = 1_000_000_007;

        for (int num : nums) {
            int diff = num - rev(num);
            int currentFreq = freqMap.getOrDefault(diff, 0);
            nicePairs = (nicePairs + currentFreq) % MOD;
            freqMap.put(diff, currentFreq + 1);
        }

        return nicePairs;
    }
}
```
### Algorithm
1. Rearrange the nice pair condition `nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])` to `nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])`.
2. Initialize a hash map, `freqMap`, to store the frequencies of the calculated differences (`num - rev(num)`).
3. Initialize `nicePairs = 0` and `MOD = 1_000_000_007`.
4. Create a helper function `rev(int n)`.
5. Iterate through each `num` in the `nums` array.
6. For each `num`, calculate `diff = num - rev(num)`.
7. Get the current frequency of `diff` from `freqMap`, let's call it `currentFreq`. `currentFreq = freqMap.getOrDefault(diff, 0)`.
8. The current number `num` can form a nice pair with all previous numbers that had the same `diff`. So, add `currentFreq` to `nicePairs`. Update `nicePairs = (nicePairs + currentFreq) % MOD`.
9. Increment the frequency of `diff` in the map: `freqMap.put(diff, currentFreq + 1)`.
10. After the loop finishes, `nicePairs` will hold the total count. Return `nicePairs`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int CountNicePairs(int[] nums) {
        Dictionary < int, int > cnt = new Dictionary < int, int > ();
        foreach(int x in nums) {
            int y = x - Rev(x);
            cnt[y] = cnt.GetValueOrDefault(y, 0) + 1;
        }
        int mod = (int) 1 e9 + 7;
        long ans = 0;
        foreach(int v in cnt.Values) {
            ans = (ans + (long) v * (v - 1) / 2) % mod;
        }
        return (int) ans;
    }
    private int Rev(int x) {
        int y = 0;
        while (x > 0) {
            y = y * 10 + x % 10;
            x /= 10;
        }
        return y;
    }
}
```

### Java

```java
class Solution {
public
  int countNicePairs(int[] nums) {
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int x : nums) {
      int y = x - rev(x);
      cnt.merge(y, 1, Integer : : sum);
    }
    final int mod = (int)1 e9 + 7;
    long ans = 0;
    for (int v : cnt.values()) {
      ans = (ans + (long)v * (v - 1) / 2) % mod;
    }
    return (int)ans;
  }
private
  int rev(int x) {
    int y = 0;
    for (; x > 0; x /= 10) {
      y = y * 10 + x % 10;
    }
    return y;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number} */ var countNicePairs = function ( nums ) { const rev = x => { let y = 0 ; for (; x > 0 ; x = Math . floor ( x / 10 )) { y = y * 10 + ( x % 10 ); } return y ; }; const cnt = new Map (); for ( const x of nums ) { const y = x - rev ( x ); cnt . set ( y , ( cnt . get ( y ) | 0 ) + 1 ); } let ans = 0 ; const mod = 1 e9 + 7 ; for ( const [ _ , v ] of cnt ) { ans = ( ans + Math . floor (( v * ( v - 1 )) / 2 )) % mod ; } return ans ; };
```

### CPP

```cpp
class Solution {
public:
  int countNicePairs(vector<int> &nums) {
    auto rev = [](int x) {
      int y = 0;
      for (; x > 0; x /= 10) {
        y = y * 10 + x % 10;
      }
      return y;
    };
    unordered_map<int, int> cnt;
    for (int &x : nums) {
      int y = x - rev(x);
      cnt[y]++;
    }
    long long ans = 0;
    const int mod = 1e9 + 7;
    for (auto &[_, v] : cnt) {
      ans = (ans + 1ll * v * (v - 1) / 2) % mod;
    }
    return ans;
  }
};

```

### Python

```python
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

```