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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Absolute Difference

Difficulty: Easy

Problem Description

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, each pair [a, b] follows:

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

Key Insights

  • The problem requires finding the minimum absolute difference between pairs of distinct integers.
  • Sorting the array simplifies the process of finding minimum differences since adjacent elements will have the smallest differences.
  • The output pairs should be in ascending order based on their values.

Space and Time Complexity

Time Complexity: O(n log n) due to the sorting step, where n is the number of elements in the array. The subsequent linear pass to find pairs takes O(n) time. Space Complexity: O(n) for storing the result pairs in the worst case.

Solution

To solve the problem, we can follow these steps:

  1. Sort the input array arr. This allows us to easily find adjacent elements with the smallest differences.
  2. Initialize a variable to track the minimum absolute difference.
  3. Iterate through the sorted array to find the minimum difference between adjacent elements.
  4. Create a list to store pairs that have this minimum difference.
  5. Return the list of pairs.

The data structure used here is a simple array (or list) to store the results, and the algorithm primarily relies on sorting followed by a linear scan.

Code Solutions

def minimumAbsDifference(arr):
    arr.sort()  # Step 1: Sort the array
    min_diff = float('inf')  # Step 2: Initialize minimum difference
    result = []  # Step 3: Result list to store pairs

    # Step 4: 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
            result = [[arr[i - 1], arr[i]]]  # Start new list of pairs
        elif diff == min_diff:
            result.append([arr[i - 1], arr[i]])  # Add to existing pairs

    return result  # Step 5: Return the result
← Back to All Questions