Count Nice Pairs in an Array
MedPrompt
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.lengthnums[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 <= 1050 <= nums[i] <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a counter
countto 0. - Define the modulo constant
MOD = 1_000_000_007. - Create a helper function
rev(int n)that returns the reverse of the integern. - Use a nested loop structure. The outer loop iterates with index
ifrom0tonums.length - 2. - The inner loop iterates with index
jfromi + 1tonums.length - 1. - Inside the inner loop, for each pair
(nums[i], nums[j]), check if the nice pair conditionnums[i] + rev(nums[j]) == nums[j] + rev(nums[i])is satisfied. - To avoid potential integer overflow during the check, cast the numbers to a
longbefore addition. - If the condition is true, increment the
count. - After the loops complete, return
count % MOD.
Walkthrough
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.
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); }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Rearrange the nice pair condition
nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])tonums[i] - rev(nums[i]) == nums[j] - rev(nums[j]). - Initialize a hash map,
freqMap, to store the frequencies of the calculated differences (num - rev(num)). - Initialize
nicePairs = 0andMOD = 1_000_000_007. - Create a helper function
rev(int n). - Iterate through each
numin thenumsarray. - For each
num, calculatediff = num - rev(num). - Get the current frequency of
difffromfreqMap, let's call itcurrentFreq.currentFreq = freqMap.getOrDefault(diff, 0). - The current number
numcan form a nice pair with all previous numbers that had the samediff. So, addcurrentFreqtonicePairs. UpdatenicePairs = (nicePairs + currentFreq) % MOD. - Increment the frequency of
diffin the map:freqMap.put(diff, currentFreq + 1). - After the loop finishes,
nicePairswill hold the total count. ReturnnicePairs.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }}/** * @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 ; };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; }};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()) % modVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.