algoadvance

You are given a list of distinct integers arr and you want to find all pairs of elements with the minimum absolute difference of any two elements. The output should be a list of pairs sorted in ascending order.

Given a list of n distinct integers, find all pairs of elements with the minimum absolute difference.

Example:
Input: arr = [4, 2, 1, 3]
Output: [[1, 2], [2, 3], [3, 4]]

Clarifying Questions

  1. Duplicates: Are there any duplicates in the array?
    • No, the problem specifies that the integers are distinct.
  2. Order: Should the pairs in the output be sorted?
    • Yes, pairs should be sorted in ascending order and also the individual pairs themselves should be in ascending order.

Strategy

  1. Sort the Array: Sorting the array will allow us to easily find the minimum absolute difference by comparing adjacent elements.
  2. Find Minimum Absolute Difference: Traverse the sorted array to find the minimum absolute difference between any two consecutive elements.
  3. Collect Pairs: Traverse the sorted array again to collect all pairs of elements that have the minimum absolute difference.
  4. Sorting Pairs: Since the pairs are formed from a sorted array and the problem specifies sorting, we will naturally get sorted pairs.

Code

def minimumAbsDifference(arr):
    arr.sort()
    min_diff = float('inf')
    result = []
    
    # Find the minimum absolute difference
    for i in range(1, len(arr)):
        diff = arr[i] - arr[i-1]
        if diff < min_diff:
            min_diff = diff
    
    # Collect all pairs with the minimum absolute difference
    for i in range(1, len(arr)):
        if arr[i] - arr[i-1] == min_diff:
            result.append([arr[i-1], arr[i]])
    
    return result

# Example usage:
arr = [4, 2, 1, 3]
print(minimumAbsDifference(arr))  # Output: [[1, 2], [2, 3], [3, 4]]

Time Complexity

Thus, the overall time complexity is [ O(n \log n) + O(n) + O(n) = O(n \log n) ]

Try our interview co-pilot at AlgoAdvance.com