Scale Engineer

Count Nice Pairs in an Array

Med
#1658Time: 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.1 company
Patterns
MathCounting
Data structures
ArrayHash Table
Companies
Block

Prompt

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

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

  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.

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.

Solutions

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;    }}

Video 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.

← Previous

Previous problem

Next →

Next problem