LeetCode 1200 - Minimum Absolute Difference

The problem asks us to find all pairs of numbers in an array that have the smallest absolute difference. In other words, given a list of distinct integers, we want to identify every pair [a, b] such that the difference b - a is minimized across all possible pairs in the array…

leetcodeeasyarraysorting

LeetCode Problem 1200

Difficulty: 🟢 Easy
Topics: Array, Sorting

Solution

Problem Understanding

The problem asks us to find all pairs of numbers in an array that have the smallest absolute difference. In other words, given a list of distinct integers, we want to identify every pair [a, b] such that the difference b - a is minimized across all possible pairs in the array, and we always list the smaller number first.

The input arr is an array of distinct integers with a length of at least 2 and up to 100,000 elements, with each element ranging from -1,000,000 to 1,000,000. The output should be a list of lists, where each inner list is a pair [a, b] sorted by the value of a, and then by b if needed.

Key points to note are that the array has distinct elements, so we do not need to worry about duplicates. Sorting the output pairs and handling negative numbers correctly are important. Edge cases could include arrays with negative numbers, arrays that are already sorted, or arrays with only two elements, which is the minimum valid size.

Approaches

The brute-force approach would involve comparing all possible pairs of numbers to compute their absolute differences. This guarantees correctness because we evaluate every pair, but it is inefficient because it requires O(n^2) operations, which is too slow for n up to 100,000.

The optimal approach relies on a key observation: the minimum absolute difference in a sorted array will always occur between consecutive elements. This is because any non-consecutive elements will have a difference at least as large as the difference between the consecutive elements in between them. Thus, by first sorting the array and then scanning through consecutive pairs, we can find the minimum difference efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Compare every pair to find the minimum difference
Optimal O(n log n) O(1) or O(n) Sort array and check consecutive differences

Algorithm Walkthrough

  1. Sort the array: Sorting ensures that consecutive elements have the smallest possible differences. Sorting takes O(n log n) time.
  2. Initialize tracking variables: Create a variable min_diff set to a very large value, and an empty list result to store pairs.
  3. Iterate through consecutive elements: Loop through the array using index i from 0 to len(arr) - 2. For each pair (arr[i], arr[i+1]), compute the difference diff = arr[i+1] - arr[i].
  4. Update minimum and result list: If diff is less than min_diff, update min_diff to diff and reset result to contain only this pair. If diff equals min_diff, append the pair to result.
  5. Return the result: After the loop, result contains all pairs with the minimum absolute difference.

Why it works: Sorting ensures that the smallest differences occur between consecutive numbers. By only comparing consecutive elements, we avoid redundant calculations while still guaranteeing we find all minimum difference pairs.

Python Solution

from typing import List

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        arr.sort()
        min_diff = float('inf')
        result = []
        
        for i in range(len(arr) - 1):
            diff = arr[i+1] - arr[i]
            if diff < min_diff:
                min_diff = diff
                result = [[arr[i], arr[i+1]]]
            elif diff == min_diff:
                result.append([arr[i], arr[i+1]])
        
        return result

The code first sorts the array to ensure consecutive elements give the smallest possible differences. It then iterates through consecutive pairs, updating min_diff and result as needed. Using a list to store pairs ensures we can return them in ascending order naturally.

Go Solution

import "sort"

func minimumAbsDifference(arr []int) [][]int {
    sort.Ints(arr)
    minDiff := int(1e7)
    result := [][]int{}
    
    for i := 0; i < len(arr)-1; i++ {
        diff := arr[i+1] - arr[i]
        if diff < minDiff {
            minDiff = diff
            result = [][]int{{arr[i], arr[i+1]}}
        } else if diff == minDiff {
            result = append(result, []int{arr[i], arr[i+1]})
        }
    }
    
    return result
}

In Go, we use sort.Ints to sort the array. We initialize minDiff with a large number to safely accommodate the maximum possible difference. Appending slices is similar to Python lists. Edge cases like negative numbers or minimal array length are naturally handled.

Worked Examples

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

After sorting: [1,2,3,4]

min_diff = inf initially.

i arr[i] arr[i+1] diff min_diff result
0 1 2 1 1 [[1,2]]
1 2 3 1 1 [[1,2],[2,3]]
2 3 4 1 1 [[1,2],[2,3],[3,4]]

Example 2: arr = [1,3,6,10,15]

After sorting: [1,3,6,10,15]

min_diff = 2 occurs between 1 and 3. Only one pair matches.

Example 3: arr = [3,8,-10,23,19,-4,-14,27]

After sorting: [-14,-10,-4,3,8,19,23,27]

Pairs with min difference 4 are [-14,-10], [19,23], [23,27].

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates, iterating through consecutive pairs is O(n)
Space O(n) For storing result pairs; sorting in Python is in-place but may use O(n) auxiliary

Sorting the array is the main cost. Tracking minimum differences and building the output list is linear in the number of pairs, which in the worst case can approach n.

Test Cases

# Basic examples
assert Solution().minimumAbsDifference([4,2,1,3]) == [[1,2],[2,3],[3,4]]  # all consecutive
assert Solution().minimumAbsDifference([1,3,6,10,15]) == [[1,3]]          # single minimum pair
assert Solution().minimumAbsDifference([3,8,-10,23,19,-4,-14,27]) == [[-14,-10],[19,23],[23,27]]

# Edge cases
assert Solution().minimumAbsDifference([1,2]) == [[1,2]]                    # smallest array
assert Solution().minimumAbsDifference([-5,-2,0,3,7]) == [[-5,-2],[0,3]]    # negative numbers
assert Solution().minimumAbsDifference([1000000,-1000000]) == [[-1000000,1000000]]  # large numbers
Test Why
[4,2,1,3] Multiple consecutive pairs with same minimum difference
[1,3,6,10,15] Only one pair has the minimum difference
[3,8,-10,23,19,-4,-14,27] Handles negative numbers and multiple minimum pairs
[1,2] Minimal input size
[-5,-2,0,3,7] Mix of negative and positive values
[1000000,-1000000] Extreme values testing integer range

Edge Cases

  1. Minimal array length: With only two elements, there is exactly one pair, which is trivially the minimum difference. The algorithm correctly returns this single pair.
  2. Negative numbers: Arrays containing negative values must still compute differences correctly. By sorting, negative numbers are handled naturally and consecutive differences remain valid.
  3. Large numbers and extreme differences: With values near ±10^6, the difference computation could overflow in some languages. In Python, integers handle arbitrary sizes. In Go, we ensure minDiff is initialized to a sufficiently large number to safely store differences without overflow.