Jobs

Interviews

Discussions

Minimum Absolute Difference

Easy

Google

6 views

Topics:

ArraysTwo Pointers

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements.

Return a list of pairs in ascending order (with respect to pairs), each pair [a, b] follows these rules:

a and b are from arr.
a < b.
b - a equals to the minimum absolute difference of any two elements in arr.

Example 1:

Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.

Example 2:

Input: arr = [1,3,6,10,15]
Output: [[1,3]]

Example 3:

Input: arr = [3,8,-10,23,19,-4,-14,27]
Output: [[-14,-10],[19,23],[23,27]]

Constraints:

2 <= arr.length <= 10^5
-10^6 <= arr[i] <= 10^6

Minimum Absolute Difference

Easy

Google

6 views

Topics:

ArraysTwo Pointers

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements.

Return a list of pairs in ascending order (with respect to pairs), each pair [a, b] follows these rules:

a and b are from arr.
a < b.
b - a equals to the minimum absolute difference of any two elements in arr.

Example 1:

Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.

Example 2:

Input: arr = [1,3,6,10,15]
Output: [[1,3]]

Example 3:

Input: arr = [3,8,-10,23,19,-4,-14,27]
Output: [[-14,-10],[19,23],[23,27]]

Constraints:

2 <= arr.length <= 10^5
-10^6 <= arr[i] <= 10^6

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 expected range of values for the integers within the input array?
Is the input array guaranteed to have at least two elements?
Can the input array contain duplicate values, and if so, how should they be handled?
Should I expect any null or empty inputs, and if so, how should I handle them?
What data type should I return for the minimum absolute difference (e.g., int, long)?

Brute Force Solution

Approach

The brute force method to find the smallest difference between any two numbers involves checking every single pair. It's like comparing each number in a group to every other number to see which pair is closest together. This ensures that we explore all the options to find the absolute minimum difference.

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

Take the first number and calculate the difference between it and every other number in the collection.
Remember the smallest difference you've found so far.
Now, take the second number and calculate the difference between it and every number (except itself and the first number, since we already did that).
If any of these new differences are smaller than the smallest one you remembered, update your smallest difference.
Continue this process with each number, comparing it to all the remaining numbers.
After you've gone through all the numbers and compared them to each other, the smallest difference you've remembered is the answer.

Code Implementation

def minimum_absolute_difference_brute_force(numbers):
    smallest_difference = float('inf')

    # Iterate through each number in the list.
    for first_number_index in range(len(numbers)):
        # Compare with remaining numbers.
        for second_number_index in range(first_number_index + 1, len(numbers)):

            # Compute absolute difference.
            current_difference = abs(numbers[first_number_index] - numbers[second_number_index])

            # Update if smaller difference is found.
            if current_difference < smallest_difference:
                smallest_difference = current_difference

    return smallest_difference

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the array, comparing each element to every other element to find the minimum absolute difference. For an array of size n, the outer loop iterates n times. The inner loop, on average, iterates approximately n/2 times, comparing each element with the remaining elements. Therefore, the total number of comparisons is proportional to n * (n/2). This simplifies to O(n²), where n is the number of elements in the input array.

Space Complexity

O(1) – The provided brute force algorithm only uses a single variable to store the minimum difference found so far. No additional data structures, such as arrays or hash maps, are created to store intermediate results or track visited elements. The space used is constant regardless of the input array size N. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

To find the smallest difference, we can't check every single pair. Instead, we first put the numbers in order. Then, because the smallest difference must be between numbers that are next to each other, we only need to check those pairs.

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

First, organize the numbers from smallest to largest.
Then, go through the ordered numbers and find the difference between each number and the one right after it.
Keep track of the smallest difference you find as you go.
In the end, the smallest difference you kept track of is the answer.

Code Implementation

def minimum_absolute_difference(numbers):
    numbers.sort()

    # Initialize min_diff to a large value.
    minimum_difference = float('inf')

    for i in range(len(numbers) - 1):
        # The minimum difference must be between
        # adjacent elements after sorting.
        current_difference = abs(numbers[i] - numbers[i + 1])

        # Track the smallest difference.
        if current_difference < minimum_difference:
            minimum_difference = current_difference

    return minimum_difference

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation impacting the time complexity is sorting the input array of n numbers. Efficient sorting algorithms, such as merge sort or quicksort, have a time complexity of O(n log n). The subsequent iteration through the sorted array to find the minimum difference involves comparing adjacent elements, which takes O(n) time. Since O(n log n) grows faster than O(n) as n increases, the overall time complexity is determined by the sorting step, resulting in O(n log n).

Space Complexity

O(1) – The algorithm sorts the input array in place. While iterating through the sorted array, it only stores a few variables, such as the current minimum difference and the indices being compared. The number of these variables remains constant regardless of the input size, N. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Empty or null input array	Return a predefined value like Integer.MAX_VALUE or throw an exception, indicating no minimum difference can be calculated.
Input array with only one element	Return a predefined value like Integer.MAX_VALUE or throw an exception, since a minimum difference requires at least two elements.
Input array with only two elements	Calculate and return the absolute difference between the two elements directly.
Input array contains duplicate values	The algorithm should correctly calculate the minimum difference even if the array contains duplicates.
Input array contains negative numbers	The absolute difference calculation should handle negative numbers correctly.
Input array contains large numbers, potentially leading to integer overflow	Use `long` data type to store the absolute difference to prevent integer overflow or use subtraction method that doesn't cause overflow.
Input array contains all identical elements	The minimum absolute difference will be 0 in this case; the algorithm should correctly identify this.
Large input array size to test for time complexity	Ensure the sorting approach used is efficient (e.g., O(n log n)) and avoids unnecessary calculations.

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 expected range of values for the integers within the input array?
Is the input array guaranteed to have at least two elements?
Can the input array contain duplicate values, and if so, how should they be handled?
Should I expect any null or empty inputs, and if so, how should I handle them?
What data type should I return for the minimum absolute difference (e.g., int, long)?

Brute Force Solution

Approach

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

Take the first number and calculate the difference between it and every other number in the collection.
Remember the smallest difference you've found so far.
Now, take the second number and calculate the difference between it and every number (except itself and the first number, since we already did that).
If any of these new differences are smaller than the smallest one you remembered, update your smallest difference.
Continue this process with each number, comparing it to all the remaining numbers.
After you've gone through all the numbers and compared them to each other, the smallest difference you've remembered is the answer.

Code Implementation

def minimum_absolute_difference_brute_force(numbers):
    smallest_difference = float('inf')

    # Iterate through each number in the list.
    for first_number_index in range(len(numbers)):
        # Compare with remaining numbers.
        for second_number_index in range(first_number_index + 1, len(numbers)):

            # Compute absolute difference.
            current_difference = abs(numbers[first_number_index] - numbers[second_number_index])

            # Update if smaller difference is found.
            if current_difference < smallest_difference:
                smallest_difference = current_difference

    return smallest_difference

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, organize the numbers from smallest to largest.
Then, go through the ordered numbers and find the difference between each number and the one right after it.
Keep track of the smallest difference you find as you go.
In the end, the smallest difference you kept track of is the answer.

Code Implementation

def minimum_absolute_difference(numbers):
    numbers.sort()

    # Initialize min_diff to a large value.
    minimum_difference = float('inf')

    for i in range(len(numbers) - 1):
        # The minimum difference must be between
        # adjacent elements after sorting.
        current_difference = abs(numbers[i] - numbers[i + 1])

        # Track the smallest difference.
        if current_difference < minimum_difference:
            minimum_difference = current_difference

    return minimum_difference

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return a predefined value like Integer.MAX_VALUE or throw an exception, indicating no minimum difference can be calculated.
Input array with only one element	Return a predefined value like Integer.MAX_VALUE or throw an exception, since a minimum difference requires at least two elements.
Input array with only two elements	Calculate and return the absolute difference between the two elements directly.
Input array contains duplicate values	The algorithm should correctly calculate the minimum difference even if the array contains duplicates.
Input array contains negative numbers	The absolute difference calculation should handle negative numbers correctly.
Input array contains large numbers, potentially leading to integer overflow	Use `long` data type to store the absolute difference to prevent integer overflow or use subtraction method that doesn't cause overflow.
Input array contains all identical elements	The minimum absolute difference will be 0 in this case; the algorithm should correctly identify this.
Large input array size to test for time complexity	Ensure the sorting approach used is efficient (e.g., O(n log n)) and avoids unnecessary calculations.