Count Nice Pairs in an Array – Java Solution

Explore Solutions in Other Languages

Code Solution


class Solution {
  public int countNicePairs(int[] nums) {
    final int kMod = 1_000_000_007;
    long ans = 0;
    Map count = new HashMap<>();

    for (final int num : nums)
      count.merge(num - rev(num), 1L, Long::sum);

    for (final long freq : count.values()) {
      ans += freq * (freq - 1) / 2;
      ans %= kMod;
    }

    return (int) ans;
  }

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

Problem Description

Counting nice pairs in an array is a bit more complex than it seems! The task is to find pairs of indices (i, j) in an array such that the difference between the number at index i and the reverse of that number is equal to the difference between the number at index j and the reverse of that number. In simpler terms, if you take a number, flip it upside down, and then see if two numbers in the array have the same “flipped” difference, you’ve got yourself a nice pair!

Imagine you’re at a party, and you see two people wearing the same outfit. You’d think, “Wow, they must be friends!” This problem is kind of like that, but instead of outfits, we’re looking for numbers that match in a very specific way.

Approach Explanation

The code uses a HashMap to count how many times each unique difference (num – rev(num)) appears in the array. For each number, it calculates this difference and updates the count. After processing all numbers, it calculates the number of nice pairs using the formula for combinations, specifically freq * (freq - 1) / 2, where freq is the count of occurrences of each difference. Finally, it returns the total count of nice pairs modulo 10^9 + 7 to avoid overflow.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n)
Space Complexity	O(n)

Real-World Example

Let’s say you’re organizing a dance-off competition. Each contestant has a unique dance move (represented by a number). You want to find pairs of contestants whose moves, when reversed, still match in a certain way. If two contestants have the same “dance move difference,” they’re considered a nice pair! This is exactly what the algorithm does, helping you find those pairs efficiently.