Domain 1EasyCORE

Minimum Absolute Difference

The problem requires finding all pairs of elements in an array that have the minimum absolute difference between them. The output should be a list of these pairs sorted in ascending order. The input is an array of distinct integers, and the constraints specify that the array length can range from 2 to (10^5), with each integer ranging from (-10^6) to (10^6).

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

1200. Minimum Absolute Difference

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 0
Acceptance rate: 67.0%


Problem Breakdown

The problem requires finding all pairs of elements in an array that have the minimum absolute difference between them. The output should be a list of these pairs sorted in ascending order. The input is an array of distinct integers, and the constraints specify that the array length can range from 2 to (10^5), with each integer ranging from (-10^6) to (10^6).

Inputs:

  • An array of distinct integers arr.

Outputs:

  • A list of pairs [a, b] where:
    • a < b
    • The absolute difference b - a is the minimum among all possible pairs in the array.

Implicit Constraints/Edge Cases:

  • The array has at least two elements.
  • All elements are distinct.
  • Negative numbers and large values are possible, so careful handling of differences is necessary.
  • The output should be sorted by the pair values.

Intuition

A brute-force approach would involve checking all possible pairs in the array to find the minimum absolute difference. This approach has a time complexity of (O(n^2)), which is inefficient given the constraints ((n \leq 10^5)).

The key insight is that by sorting the array first, we can reduce the problem to a linear scan where we only need to compare adjacent elements. Sorting takes (O(n \log n)) time, and finding the minimum difference in a sorted array takes (O(n)) time. This combined approach is much more efficient.

Approach

  1. Sort the Array: Begin by sorting the array arr. This will allow us to only consider adjacent elements when calculating differences.
  2. Initialize Variables:
    • min_diff: Set it to a large value initially (e.g., infinity) to ensure any real difference found will be smaller.
    • result: An empty list to store pairs with the minimum absolute difference.
  3. Find Minimum Difference:
    • Iterate through the sorted array and calculate the difference between each pair of adjacent elements.
    • If a new minimum difference is found, update min_diff and reset result to contain only this new pair.
    • If the current difference equals min_diff, append the pair to result.
  4. Return Result: The list result will contain all pairs with the minimum absolute difference in ascending order.

Complexity Analysis

  • Time Complexity: (O(n \log n)) due to the sorting step, where (n) is the length of the array.
  • Space Complexity: (O(1)) for the additional variables used (excluding the space required for sorting and the output list).

Solution

def minimumAbsDifference(arr):
    # Step 1: Sort the array
    arr.sort()
    
    # Step 2: Initialize variables
    min_diff = float('inf')
    result = []
    
    # Step 3: 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]]]
        elif diff == min_diff:
            result.append([arr[i - 1], arr[i]])
    
    # Step 4: Return the result
    return result

Edge Cases Handled

  • Sorted Array: If the array is already sorted, the algorithm will still work correctly as it only relies on adjacent elements.
  • All Elements Same Difference: If all pairs have the same minimum difference, the algorithm will collect all such pairs in the result.
  • Negative Numbers and Large Values: The sorting and difference calculation handle negative numbers and large values naturally without overflow issues.