Scale Engineer

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
AgodaIBMJ.P. MorganPayPal

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 <= 105
  • -106 <= arr[i] <= 106

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.

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

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.

Solutions

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

Next problem