Minimum Absolute Difference

EASY

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(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

Checkout 2 different approaches to solve Minimum Absolute Difference. Click on different approaches to view the approach and algorithm in detail.

Brute Force Approach

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.

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.

import java.util.*;

class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        int minDifference = Integer.MAX_VALUE;
        List<List<Integer>> resultPairs = new ArrayList<>();

        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                int diff = Math.abs(arr[i] - arr[j]);

                if (diff < minDifference) {
                    minDifference = diff;
                    resultPairs.clear();
                    List<Integer> pair = new ArrayList<>();
                    pair.add(Math.min(arr[i], arr[j]));
                    pair.add(Math.max(arr[i], arr[j]));
                    resultPairs.add(pair);
                } else if (diff == minDifference) {
                    List<Integer> pair = new ArrayList<>();
                    pair.add(Math.min(arr[i], arr[j]));
                    pair.add(Math.max(arr[i], arr[j]));
                    resultPairs.add(pair);
                }
            }
        }

        // Sort the final list of pairs as required
        Collections.sort(resultPairs, (a, b) -> a.get(0).compareTo(b.get(0)));

        return resultPairs;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Minimum Absolute Difference. Click on different languages to view the code.

class 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 ; } }

Video Solution

Watch the video walkthrough for Minimum Absolute Difference

Algorithms:

Sorting

Data Structures:

Array

Companies:

Agoda |IBM |J.P. Morgan |PayPal |