Start by recognizing that a nice pair satisfies nums[i] + rev(nums[j]) == nums[j] + rev(nums[i]). Rearranging gives nums[i] - rev(nums[i]) == nums[j] - rev(nums[j]), which allows a hash map to count occurrences efficiently. Iterate through the array, store frequencies of nums[i] - rev(nums[i]), and sum valid combinations modulo 10^9+7 to handle large results.
Problem Statement
You are given an array of non-negative integers nums. Define rev(x) as the integer obtained by reversing the digits of x. A pair of indices (i, j) is considered nice if i < j and nums[i] + rev(nums[j]) equals nums[j] + rev(nums[i]). Your task is to count all such nice pairs efficiently.
Return the total number of nice pairs modulo 10^9 + 7. Constraints: 1 <= nums.length <= 10^5 and 0 <= nums[i] <= 10^9. For example, nums = [42,11,1,97] produces 2 nice pairs because (0,3) and (1,2) satisfy the condition.
Examples
Example 1
Input: nums = [42,11,1,97]
Output: 2
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
Example details omitted.
Constraints
- 1 <= nums.length <= 105
- 0 <= nums[i] <= 109
Solution Approach
Transform the problem using subtraction
Rewrite the nice pair condition as nums[i] - rev(nums[i]) == nums[j] - rev(nums[j]). This converts the problem into counting equal differences, which simplifies scanning and avoids redundant pair checks.
Use a hash map for frequency counting
Iterate through nums and calculate the key as nums[i] - rev(nums[i]). Store the frequency of each key in a hash map. Each time a key repeats, it forms as many new nice pairs as the current count, allowing O(n) accumulation.
Apply modulo arithmetic for large totals
Since the number of nice pairs can be very large, maintain the running total modulo 10^9 + 7. This prevents integer overflow and ensures the result fits the problem constraints.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(n) |
Time complexity is O(n) because each element is processed once. Space complexity is O(n) for the hash map storing difference counts.
What Interviewers Usually Probe
- Look for an O(n^2) brute force first but quickly pivot to hash-based counting.
- Expect candidates to notice the subtraction transformation nums[i] - rev(nums[i]).
- Emphasize handling modulo arithmetic correctly to prevent overflow.
Common Pitfalls or Variants
Common pitfalls
- Attempting nested loops leads to O(n^2) and timeouts on large arrays.
- Forgetting to reverse numbers correctly can produce incorrect counts.
- Neglecting modulo 10^9+7 results in integer overflow for large arrays.
Follow-up variants
- Count pairs where nums[i] + rev(nums[j]) - nums[j] - rev(nums[i]) equals a target value instead of zero.
- Find nice pairs in a subarray or with additional constraints on index distance.
- Return the actual index pairs rather than just the count, preserving order.
How GhostInterview Helps
- Automatically rewrites the problem condition into the hash-map friendly form nums[i] - rev(nums[i]).
- Guides through frequency accumulation and modulo handling to prevent common mistakes.
- Simulates the array scanning pattern to verify pair counting with step-by-step checks.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main trick to solve Count Nice Pairs in an Array efficiently?
The key is transforming the condition into nums[i] - rev(nums[i]) == nums[j] - rev(nums[j]) and using a hash map to count frequencies.
Why do we use modulo 10^9+7 in this problem?
The number of nice pairs can be very large, and modulo prevents integer overflow while satisfying problem constraints.
Can we use a nested loop for Count Nice Pairs?
Yes, but nested loops lead to O(n^2) time complexity, which is too slow for arrays of size up to 10^5.
How do you reverse numbers correctly in this context?
Convert the number to a string, reverse the string, then convert back to integer, handling leading zeros appropriately.
Does GhostInterview help with verifying large input arrays?
Yes, it simulates hash-based counting and ensures the modulo arithmetic is applied correctly for large arrays.
Need direct help with Count Nice Pairs in an Array instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Count Nice Pairs in an Array from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the number of good subsets in an integer array, where each subset's product is the product of distinct primes.
Open problem page#2001 Number of Pairs of Interchangeable RectanglesCount all pairs of rectangles that share the exact width-to-height ratio using efficient array scanning and hash lookup.
Open problem page#1512 Number of Good PairsCount all index pairs in an array where elements match and the first index is smaller, using hash-based scanning efficiently.
Open problem page