We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Absolute Difference

Number: 1306

Difficulty: Easy

Paid? No

Companies: IBM, Bloomberg, Oracle, Agoda, Google, Salesforce, PayPal, J.P. Morgan, Amazon, Audible

Problem Description

Given an array of distinct integers, find all pairs of elements with the minimum absolute difference of any two elements. Each pair [a, b] must satisfy a < b and the pair's difference must match the smallest absolute difference found in the array. The final list should be in ascending order.

Key Insights

  • Sorting the input array will allow efficient comparison of adjacent elements.
  • The minimum absolute difference can only be among pairs of consecutive elements after sorting.
  • Only one pass through the sorted array is needed to determine the minimum difference and collect the corresponding pairs.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the array. Space Complexity: O(n) for storing the sorted array and the final result.

Solution

The solution involves first sorting the input array. This sorting step ensures that the smallest differences are between consecutive elements. Next, make a single pass over the sorted array to compute the differences between adjacent pairs. Keep track of the minimum difference encountered. Then, iterate again (or concurrently) to collect all pairs that match this minimum difference. This approach uses sorting and a simple iteration, which minimizes the need for additional data structures beyond the final result list.

Code Solutions

# Sort the array
def minimumAbsDifference(arr):
    # Sort the input list in ascending order
    arr.sort()
    
    # Initialize variables to store the minimum difference found and the result list
    min_diff = float('inf')
    result = []
    
    # Iterate through the array, comparing consecutive elements
    for i in range(1, len(arr)):
        diff = arr[i] - arr[i - 1]
        # If a smaller difference is found, update min_diff and reset the result list
        if diff < min_diff:
            min_diff = diff
            result = [[arr[i - 1], arr[i]]]
        # If the current difference equals the minimum difference, append to result
        elif diff == min_diff:
            result.append([arr[i - 1], arr[i]])
    
    return result

# Example Usage
print(minimumAbsDifference([4, 2, 1, 3]))
← Back to All Questions