Jobs

Interviews

Discussions

Count Nice Pairs in an Array

Medium

Block

1 view

Topics:

ArraysTwo Pointers

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 10⁹ + 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 <= 10⁵
0 <= nums[i] <= 10⁹

Try coding it in LeetCode

Count Nice Pairs in an Array

Medium

Block

1 view

Topics:

ArraysTwo Pointers

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 10⁹ + 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 <= 10⁵
0 <= nums[i] <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array, and can the array contain negative numbers or zeros?
What is the maximum size of the input array?
If no nice pairs exist, what value should I return?
Are duplicate numbers within the array allowed, and if so, how should they be handled when determining 'nice pairs'?
Could you clarify the definition of a 'nice pair'? Specifically, what happens if the reversed version of a number has leading zeros?

Brute Force Solution

Approach

The brute force approach to counting nice pairs is straightforward. We're going to check every possible pair of numbers in the list to see if it's a 'nice pair'. If it is, we add it to our total count.

Here's how the algorithm would work step-by-step:

Take the first number in the list.
Compare it with every other number in the list, including itself.
For each comparison, check if the pair is 'nice' according to the given rule (add number to its reverse and check if the sum is zero).
If the pair is 'nice', increase the count.
Move to the next number in the list.
Repeat the process of comparing it with every other number in the list and checking if they form a 'nice' pair.
Continue this process until you've gone through every number in the list.
The final count will be the total number of 'nice' pairs found.

Code Implementation

def count_nice_pairs_brute_force(numbers):
    number_of_nice_pairs = 0
    array_length = len(numbers)

    for first_index in range(array_length):
        for second_index in range(array_length):
            # Checking every pair including itself.
            first_number = numbers[first_index]
            second_number = numbers[second_index]
            reversed_second_number = int(str(second_number)[::-1])

            # Check for the condition to increment.
            if first_number + reversed_second_number == second_number + int(str(first_number)[::-1]):
                number_of_nice_pairs += 1

    # Divide by two to avoid overcounting, since pairs are counted twice.
    number_of_nice_pairs = number_of_nice_pairs // 2

    return number_of_nice_pairs

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force approach involves iterating through each of the n elements in the input array. For each element, it compares it with every other element in the array, resulting in a nested loop structure. This pair-checking operation is performed for all possible pairs of elements. Therefore, the total number of operations is proportional to n * n, which simplifies to O(n²).

Space Complexity

O(1) – The provided brute force algorithm iterates through pairs of numbers in the input list without using any auxiliary data structures. It only needs to store a constant number of variables such as loop counters or temporary variables for calculations, irrespective of the input size N (where N is the number of elements in the list). Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

To find nice pairs efficiently, we need to avoid comparing every single pair. The key idea is to transform the problem into a counting problem using a clever mathematical trick, then use a tool to count things efficiently.

Here's how the algorithm would work step-by-step:

First, for each number in the list, calculate the difference between the number and its reverse.
Then, count how many times each difference appears in the resulting list of differences. Think of this like grouping together numbers that have the same difference value.
For each unique difference value, if that value appears a certain number of times, calculate how many pairs you can make with that many numbers. For example, if a difference appears 3 times, you can make 3 pairs. If a difference appears 4 times, you can make 6 pairs.
Add up the number of pairs you can make for each unique difference. This final sum is the total number of "nice" pairs in the original list.

Code Implementation

def count_nice_pairs(numbers):
    differences = {}
    count_of_nice_pairs = 0

    for number in numbers:
        number_reversed = int(str(number)[::-1])
        difference = number - number_reversed

        # Use a dictionary to count the occurrences of each difference
        if difference in differences:
            differences[difference] += 1
        else:
            differences[difference] = 1

    # Iterate through the counts of each difference to calculate pairs
    for difference_count in differences.values():
        # Calculate number of pairs for each difference value
        count_of_nice_pairs += (difference_count * (difference_count - 1)) // 2

    return count_of_nice_pairs

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n to calculate the difference between each number and its reverse. Then, it uses a hash map (or similar data structure) to count the frequency of each difference, which takes O(n) time on average. Finally, it iterates through the unique differences (at most n) to calculate the number of pairs for each difference, which also takes O(n) time. Thus, the overall time complexity is dominated by these linear operations, resulting in O(n).

Space Complexity

O(N) – The algorithm calculates the difference between each number and its reverse and stores these differences. This results in a list of differences with a size proportional to the input array's size, N. Additionally, it counts the occurrences of each unique difference, which is stored in a hash map (or dictionary) that, in the worst case, could store N unique differences. Therefore, the auxiliary space used is proportional to N.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as no pairs can be formed.
Array with a single element	Return 0 as a single element cannot form a pair.
Array containing negative numbers	The reversing and addition operation should handle negative numbers correctly, so no special handling needed.
Array containing zero	Zero reversed is zero, so handle as any normal number.
Integer overflow during the reversing operation.	Use long to store the reversed number to prevent overflow.
Large input array (performance)	Use HashMap to achieve an O(n) time complexity; a naive O(n^2) approach may timeout.
Array contains duplicate numbers that form a pair with themselves	The counts of each reversed number difference in the hashmap correctly accounts for duplicate combinations.
Extreme boundary values (Integer.MAX_VALUE and Integer.MIN_VALUE)	Ensure reversal and subtraction operations handle these without unexpected overflows by using long data type.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array, and can the array contain negative numbers or zeros?
What is the maximum size of the input array?
If no nice pairs exist, what value should I return?
Are duplicate numbers within the array allowed, and if so, how should they be handled when determining 'nice pairs'?
Could you clarify the definition of a 'nice pair'? Specifically, what happens if the reversed version of a number has leading zeros?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first number in the list.
Compare it with every other number in the list, including itself.
For each comparison, check if the pair is 'nice' according to the given rule (add number to its reverse and check if the sum is zero).
If the pair is 'nice', increase the count.
Move to the next number in the list.
Repeat the process of comparing it with every other number in the list and checking if they form a 'nice' pair.
Continue this process until you've gone through every number in the list.
The final count will be the total number of 'nice' pairs found.

Code Implementation

def count_nice_pairs_brute_force(numbers):
    number_of_nice_pairs = 0
    array_length = len(numbers)

    for first_index in range(array_length):
        for second_index in range(array_length):
            # Checking every pair including itself.
            first_number = numbers[first_index]
            second_number = numbers[second_index]
            reversed_second_number = int(str(second_number)[::-1])

            # Check for the condition to increment.
            if first_number + reversed_second_number == second_number + int(str(first_number)[::-1]):
                number_of_nice_pairs += 1

    # Divide by two to avoid overcounting, since pairs are counted twice.
    number_of_nice_pairs = number_of_nice_pairs // 2

    return number_of_nice_pairs

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, for each number in the list, calculate the difference between the number and its reverse.
Then, count how many times each difference appears in the resulting list of differences. Think of this like grouping together numbers that have the same difference value.
For each unique difference value, if that value appears a certain number of times, calculate how many pairs you can make with that many numbers. For example, if a difference appears 3 times, you can make 3 pairs. If a difference appears 4 times, you can make 6 pairs.
Add up the number of pairs you can make for each unique difference. This final sum is the total number of "nice" pairs in the original list.

Code Implementation

def count_nice_pairs(numbers):
    differences = {}
    count_of_nice_pairs = 0

    for number in numbers:
        number_reversed = int(str(number)[::-1])
        difference = number - number_reversed

        # Use a dictionary to count the occurrences of each difference
        if difference in differences:
            differences[difference] += 1
        else:
            differences[difference] = 1

    # Iterate through the counts of each difference to calculate pairs
    for difference_count in differences.values():
        # Calculate number of pairs for each difference value
        count_of_nice_pairs += (difference_count * (difference_count - 1)) // 2

    return count_of_nice_pairs

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as no pairs can be formed.
Array with a single element	Return 0 as a single element cannot form a pair.
Array containing negative numbers	The reversing and addition operation should handle negative numbers correctly, so no special handling needed.
Array containing zero	Zero reversed is zero, so handle as any normal number.
Integer overflow during the reversing operation.	Use long to store the reversed number to prevent overflow.
Large input array (performance)	Use HashMap to achieve an O(n) time complexity; a naive O(n^2) approach may timeout.
Array contains duplicate numbers that form a pair with themselves	The counts of each reversed number difference in the hashmap correctly accounts for duplicate combinations.
Extreme boundary values (Integer.MAX_VALUE and Integer.MIN_VALUE)	Ensure reversal and subtraction operations handle these without unexpected overflows by using long data type.