Minimum Absolute Difference

Easy

#1123Time: O(N^2). The nested loops result in comparing every pair of elements, which is N * (N-1) / 2 comparisons. This quadratic complexity makes it too slow for the given constraints.Space: O(N), in the worst-case scenario where many pairs have the same minimum difference (e.g., for an input like `[1, 2, 3, 4]`, the result has `N-1` pairs). This space is used to store the result list.6 companies

Algorithms

Sorting

Data structures

Array

Companies

Agoda IBM J.P. Morgan PayPal

Prompt

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(with respect to pairs), 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

Example 1:

Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.

Example 2:

Input: arr = [1,3,6,10,15]
Output: [[1,3]]

Example 3:

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

Constraints:

2 <= arr.length <= 10⁵
-10⁶ <= arr[i] <= 10⁶

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves a straightforward, brute-force method of comparing every possible pair of elements in the array. For each pair, we calculate the absolute difference and keep track of the minimum difference found so far. We store all pairs that match this minimum difference.

Algorithm

Initialize a variable minDifference to a very large value (e.g., Integer.MAX_VALUE).
Initialize an empty list of lists, resultPairs, to store the final pairs.
Use a nested loop structure. The outer loop iterates from i = 0 to n-1 and the inner loop from j = i + 1 to n-1.
For each pair (arr[i], arr[j]), calculate the absolute difference currentDifference = Math.abs(arr[i] - arr[j]).
If currentDifference is less than minDifference:
- Update minDifference with currentDifference.
- Clear the resultPairs list.
- Add the current pair, sorted as [min(arr[i], arr[j]), max(arr[i], arr[j])], to resultPairs.
If currentDifference is equal to minDifference:
- Add the current pair, sorted, to resultPairs.
After iterating through all pairs, sort the resultPairs list based on the first element of each pair.
Return resultPairs.

Walkthrough

In this method, we iterate through the array with two nested loops to generate every unique pair of numbers. We maintain a variable, minDifference, to store the smallest absolute difference encountered. As we iterate, we compare the difference of the current pair with minDifference.

If the current pair's difference is smaller than minDifference, we've found a new minimum. We update minDifference, clear our result list (as all previously found pairs are now invalid), and add the current pair to the result list. If the current pair's difference is equal to minDifference, we simply add it to our result list.

Because the pairs are added as they are found, the final list of pairs is not guaranteed to be in ascending order. Therefore, a final sorting step is required on the result list before returning it.

1import java.util.*;2 3class Solution {4    public List<List<Integer>> minimumAbsDifference(int[] arr) {5        int minDifference = Integer.MAX_VALUE;6        List<List<Integer>> resultPairs = new ArrayList<>();7 8        for (int i = 0; i < arr.length; i++) {9            for (int j = i + 1; j < arr.length; j++) {10                int diff = Math.abs(arr[i] - arr[j]);11 12                if (diff < minDifference) {13                    minDifference = diff;14                    resultPairs.clear();15                    List<Integer> pair = new ArrayList<>();16                    pair.add(Math.min(arr[i], arr[j]));17                    pair.add(Math.max(arr[i], arr[j]));18                    resultPairs.add(pair);19                } else if (diff == minDifference) {20                    List<Integer> pair = new ArrayList<>();21                    pair.add(Math.min(arr[i], arr[j]));22                    pair.add(Math.max(arr[i], arr[j]));23                    resultPairs.add(pair);24                }25            }26        }27 28        // Sort the final list of pairs as required29        Collections.sort(resultPairs, (a, b) -> a.get(0).compareTo(b.get(0)));30 31        return resultPairs;32    }33}

Complexity

Time

O(N^2). The nested loops result in comparing every pair of elements, which is N * (N-1) / 2 comparisons. This quadratic complexity makes it too slow for the given constraints.

Space

O(N), in the worst-case scenario where many pairs have the same minimum difference (e.g., for an input like `[1, 2, 3, 4]`, the result has `N-1` pairs). This space is used to store the result list.

Trade-offs

Pros

Simple to understand and implement.
Does not require modifying the original array (if a copy is made).

Cons

Highly inefficient due to the O(N^2) time complexity.
Will likely result in a 'Time Limit Exceeded' error for large input arrays as specified in the constraints.

A much more efficient approach is to first sort the array. The key insight is that the minimum absolute difference between any two elements in the array will always occur between two adjacent elements in the sorted array. This reduces the problem from comparing all O(N^2) pairs to just O(N) adjacent pairs.

Algorithm

First, sort the input array arr in ascending order.
Initialize a variable minDifference to Integer.MAX_VALUE.
Initialize an empty list of lists, resultPairs.
Iterate through the sorted array from i = 0 to n-2 (i.e., up to the second-to-last element).
In each iteration, calculate the difference between adjacent elements: currentDifference = arr[i+1] - arr[i].
Compare currentDifference with minDifference:
- If currentDifference < minDifference, a new minimum is found. Update minDifference, clear resultPairs, and add the current pair [arr[i], arr[i+1]].
- If currentDifference == minDifference, add the current pair [arr[i], arr[i+1]] to resultPairs.
After the loop, return resultPairs. No final sorting is needed as pairs are added in ascending order.

Walkthrough

The logic behind this approach is that for any three numbers a < b < c, the difference c - a is equal to (c - b) + (b - a). Since both (c - b) and (b - a) are positive, c - a must be greater than both b - a and c - b. This property implies that we only need to check the differences between adjacent elements after sorting the array to find the global minimum difference.

The algorithm proceeds as follows:

Sort the input array arr.
Make a single pass through the sorted array, from the first to the second-to-last element.
During the pass, keep track of the minimum difference found so far. If we find a pair of adjacent elements with a difference smaller than the current minimum, we update the minimum and clear our result list, adding this new pair. If we find a pair with a difference equal to the current minimum, we just add it to the result list.

This single-pass approach after sorting is efficient and ensures the final list of pairs is already sorted, as we process the elements in increasing order.

1import java.util.*;2 3class Solution {4    public List<List<Integer>> minimumAbsDifference(int[] arr) {5        // 1. Sort the array6        Arrays.sort(arr);7 8        List<List<Integer>> resultPairs = new ArrayList<>();9        int minDifference = Integer.MAX_VALUE;10 11        // 2. Single pass to find min difference and collect pairs12        for (int i = 0; i < arr.length - 1; i++) {13            int currentDifference = arr[i+1] - arr[i];14 15            if (currentDifference < minDifference) {16                minDifference = currentDifference;17                resultPairs.clear();18                resultPairs.add(Arrays.asList(arr[i], arr[i+1]));19            } else if (currentDifference == minDifference) {20                resultPairs.add(Arrays.asList(arr[i], arr[i+1]));21            }22        }23 24        return resultPairs;25    }26}

Complexity

Time

O(N log N). The dominant operation is sorting the array. The subsequent single pass to find the minimum difference and collect pairs takes O(N) time. Therefore, the total time complexity is O(N log N).

Space

O(N). The space complexity of the sorting algorithm (`Arrays.sort` in Java for primitives) is O(log N) on average for the recursion stack. However, the space required for the output list can be up to O(N) in the worst case. Thus, the overall space complexity is dominated by the output list, making it O(N).

Trade-offs

Pros

Highly efficient with a time complexity of O(N log N), which passes the given constraints.
The logic is clean and relies on a powerful property of sorted sequences.
The resulting list of pairs is naturally sorted, avoiding an explicit sorting step on the final list.

Cons

The primary cost is the initial sort, which might not be ideal if the array is already partially sorted or if sorting is expensive for other reasons.
The space complexity for sorting can be O(N) in some language implementations, although it's often O(log N).

Solutions

Solution

1class Solution { public List < List < Integer >> minimumAbsDifference ( int [] arr ) { Arrays . sort ( arr ); int n = arr . length ; int mi = 1 << 30 ; for ( int i = 0 ; i < n - 1 ; ++ i ) { mi = Math . min ( mi , arr [ i + 1 ] - arr [ i ]); } List < List < Integer >> ans = new ArrayList <>(); for ( int i = 0 ; i < n - 1 ; ++ i ) { if ( arr [ i + 1 ] - arr [ i ] == mi ) { ans . add ( List . of ( arr [ i ], arr [ i + 1 ])); } } return ans ; } }

1class Solution { public: vector < vector < int >> minimumAbsDifference ( vector < int >& arr ) { sort ( arr . begin (), arr . end ()); int mi = 1 << 30 ; int n = arr . size (); for ( int i = 0 ; i < n - 1 ; ++ i ) { mi = min ( mi , arr [ i + 1 ] - arr [ i ]); } vector < vector < int >> ans ; for ( int i = 0 ; i < n - 1 ; ++ i ) { if ( arr [ i + 1 ] - arr [ i ] == mi ) { ans . push_back ({ arr [ i ], arr [ i + 1 ]}); } } return ans ; } };

1class Solution : def minimumAbsDifference ( self , arr : List [ int ]) -> List [ List [ int ]]: arr . sort () mi = min ( b - a for a , b in pairwise ( arr )) return [[ a , b ] for a , b in pairwise ( arr ) if b - a == mi ]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem