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] <= 109For a nice pair, nums[i] + rev(nums[j]) = nums[j] + rev(nums[i]) implies nums[i] - rev(nums[i]) = nums[j] - rev(nums[j]). Use this invariant property to compute measurable differences for each index.
Transform each element nums[i] in the array to nums[i] - rev(nums[i]). Count the frequency of each difference to compute the number of pairs (i, j) with this characteristic efficiently.
The solution builds on the idea that the equation nums[i] - rev(nums[i]) == nums[j] - rev(nums[j]) describes a relationship that clearly defines a valid condition for 'nice' index pairs.
Every time a particular difference is encountered, we count how many times it has appeared previously to compute how many pairs can be formed based on past occurrences, thus avoiding a direct double loop and optimizing for time complexity.
Java
Time Complexity: O(N), where N is the length of the nums array since we process each number in the array in constant time.
Space Complexity: O(N), for storing the frequencies of differences.
Another less efficient, but intuitive approach is to use a two-pointer technique to check each pair (i, j) for the nice pair condition. This approach isn't time optimized for large input sizes but serves to clearly enforce the criteria pairwise and verify the conditions directly.
This method involves going through each pair directly to see if the condition holds. Although easy to think about, it is not suitable for large-sized arrays.
This C implementation uses two nested loops to check each pair of indices. It calculates the reverse of both numbers and compares their sum to find nice pairs.
It's a straightforward approach that leverages direct pairwise comparison, but this results in less efficiency for large inputs. Suitable for educational purposes or small arrays, it helps grasp the mechanics without advanced data structures.
C++
Time Complexity: O(N²), where N is the size of the array, due to the pairwise comparison.
Space Complexity: O(1), constant space as no additional data structures are used.
| Approach | Complexity |
|---|---|
| Using Difference with Reverse Approach | Time Complexity: O(N), where N is the length of the nums array since we process each number in the array in constant time. Space Complexity: O(N), for storing the frequencies of differences. |
| Two-Pointer Approach (Pairwise Check) | Time Complexity: O(N²), where N is the size of the array, due to the pairwise comparison. Space Complexity: O(1), constant space as no additional data structures are used. |
Count Nice Pairs in an Array | Simple Clean | Important suggestion | AMAZON | Leetcode-1814 • codestorywithMIK • 4,872 views views
Watch 9 more video solutions →Practice Count Nice Pairs in an Array with our built-in code editor and test cases.
Practice on FleetCode