Problem Description

You are given an array of distinct integers arr. Your task is to find all pairs of elements that have the minimum absolute difference among all possible pairs in the array.

The problem asks you to:

1. Find the minimum absolute difference between any two elements in the array
2. Return all pairs [a, b] that have this minimum difference

Each pair in your result must satisfy these conditions:

• Both a and b come from the original array arr
• a < b (the smaller element comes first in the pair)
• The difference b - a equals the minimum absolute difference found in step 1

The pairs should be returned in ascending order.

For example, if arr = [4, 2, 1, 3], after sorting we get [1, 2, 3, 4]. The differences between adjacent elements are: 2-1=1, 3-2=1, 4-3=1. The minimum difference is 1. So we return all pairs with difference 1: [[1,2], [2,3], [3,4]].

The solution approach sorts the array first because the minimum absolute difference will always occur between adjacent elements in a sorted array. After sorting, it finds the minimum difference by checking all adjacent pairs, then collects all pairs that have this minimum difference.

Intuition

The key insight is that in an unsorted array, we'd need to check every possible pair to find the minimum difference, which would take O(n²) time. However, we can make an important observation: the minimum absolute difference between any two elements will always occur between elements that are close to each other in value.

Think about it this way - if we have numbers like [10, 3, 15, 7], the smallest difference won't be between 3 and 15 (difference of 12), but rather between numbers that are numerically closer, like 7 and 10 (difference of 3).

This naturally leads us to sorting the array first. Once sorted, elements with similar values become adjacent to each other. For instance, [3, 7, 10, 15]. Now we can guarantee that the minimum absolute difference must exist between some pair of adjacent elements. Why? Because for any element, its closest neighbors in value are the elements immediately before and after it in the sorted array.

After sorting, we make two passes through the array:

1. First pass: Check all adjacent pairs to find the minimum difference value
2. Second pass: Collect all adjacent pairs that have this minimum difference

The beauty of this approach is that we reduce the problem from checking all n*(n-1)/2 pairs to just checking n-1 adjacent pairs. Since the array contains distinct integers, we don't need to worry about duplicate values, and the pairs naturally come out in ascending order because we're traversing a sorted array from left to right.

Learn more about Sorting patterns.

Solution Approach

The solution follows a straightforward approach using sorting and two passes through the array:

Step 1: Sort the array

arr.sort()

We sort the array in ascending order. This ensures that elements close in value become adjacent, allowing us to find the minimum difference by only checking consecutive pairs.

Step 2: Find the minimum absolute difference

mi = min(b - a for a, b in pairwise(arr))

We use the pairwise function to iterate through all adjacent pairs (a, b) in the sorted array. For each pair, we calculate the difference b - a (which is always positive since the array is sorted). The min() function finds the smallest difference among all adjacent pairs.

The pairwise(arr) function generates consecutive pairs from the array. For example, if arr = [1, 3, 6, 10], then pairwise(arr) yields (1, 3), (3, 6), (6, 10).

Step 3: Collect all pairs with minimum difference

return [[a, b] for a, b in pairwise(arr) if b - a == mi]

We make another pass through the adjacent pairs using list comprehension. For each pair (a, b), we check if the difference b - a equals the minimum difference mi we found. If it does, we include the pair [a, b] in our result list.

Time Complexity: O(n log n) where n is the length of the array. The sorting step dominates the time complexity.

Space Complexity: O(1) if we don't count the output array. The sorting can be done in-place, and we only use a constant amount of extra space for the variable mi.

Example Walkthrough

Let's walk through the solution with arr = [40, 11, 26, 27, -20].

Step 1: Sort the array After sorting: arr = [-20, 11, 26, 27, 40]

Step 2: Find the minimum absolute difference We examine all adjacent pairs:

• Pair (-20, 11): difference = 11 - (-20) = 31
• Pair (11, 26): difference = 26 - 11 = 15
• Pair (26, 27): difference = 27 - 26 = 1
• Pair (27, 40): difference = 40 - 27 = 13

The minimum difference is 1.

Step 3: Collect all pairs with minimum difference We go through the adjacent pairs again and collect those with difference equal to 1:

• Pair (-20, 11): difference = 31 ≠ 1 (skip)
• Pair (11, 26): difference = 15 ≠ 1 (skip)
• Pair (26, 27): difference = 1 = 1 ✓ (include)
• Pair (27, 40): difference = 13 ≠ 1 (skip)

Result: [[26, 27]]

The final answer contains only one pair because [26, 27] is the only adjacent pair in the sorted array with the minimum difference of 1.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by the sorting operation arr.sort(), which takes O(n × log n) time where n is the length of the input array. After sorting, the code performs two linear passes through the array using pairwise(arr):

• First pass to find the minimum difference: O(n-1) = O(n)
• Second pass to collect pairs with minimum difference: O(n-1) = O(n)

Overall: O(n × log n) + O(n) + O(n) = O(n × log n)

Space Complexity: O(log n)

The space complexity consists of:

• The sorting algorithm (Timsort in Python) uses O(log n) space for its recursive call stack
• The pairwise iterator creates pairs on-the-fly without storing them all, using O(1) space
• The output list is not counted as part of space complexity (it's the required output)
• The variable mi uses O(1) space

Therefore, the dominant space usage comes from the sorting algorithm, giving us O(log n) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Searching for minimum difference across all pairs (not just adjacent)

The Mistake: A common error is attempting to check all possible pairs in the array to find the minimum difference, leading to unnecessary O(n²) comparisons:

# Inefficient approach - checking all pairs
min_diff = float('inf')
for i in range(len(arr)):
    for j in range(i + 1, len(arr)):
        min_diff = min(min_diff, abs(arr[j] - arr[i]))

Why it happens: It seems logical to check every possible pair since we want the "minimum absolute difference among all possible pairs."

The Solution: After sorting, the minimum absolute difference will always occur between adjacent elements. This is because for any three sorted numbers a < b < c, we have |b - a| < |c - a| and |c - b| < |c - a|. Therefore, we only need to check consecutive pairs:

arr.sort()
min_diff = float('inf')
for i in range(1, len(arr)):
    min_diff = min(min_diff, arr[i] - arr[i-1])

Pitfall 2: Forgetting to sort the array first

The Mistake:

# Wrong - trying to find pairs without sorting
result = []
min_diff = # ... find min diff somehow
for i in range(len(arr)):
    for j in range(i + 1, len(arr)):
        if abs(arr[j] - arr[i]) == min_diff:
            result.append([min(arr[i], arr[j]), max(arr[i], arr[j])])

Why it happens: The problem statement doesn't explicitly mention sorting, and one might think we need to preserve the original array order.

The Solution: Always sort first. The problem requires pairs in ascending order anyway, and sorting makes finding the minimum difference efficient:

arr.sort()  # Critical first step
# Now we can efficiently find min diff and pairs

Pitfall 3: Not handling the pair order correctly

The Mistake:

# Wrong - might add pairs in wrong order
if arr[i] - arr[i-1] == min_diff:
    result.append([arr[i], arr[i-1]])  # Wrong order!

Why it happens: After sorting, it's easy to forget that we need [smaller, larger] format for each pair.

The Solution: Since the array is sorted, arr[i-1] is always less than arr[i], so the correct order is:

result.append([arr[i-1], arr[i]])  # Correct: smaller element first