Minimum Absolute Difference

Easy
369.

Minimum Absolute Difference

Minimum Absolute Difference is an easy coding problem on arrays and sorting, asked in Amazon and Adobe interviews.

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference between them.

Return the pairs in ascending order, each pair written as [a, b] with a < b.

Example 1

Input
arr = [4,2,1,3]
Output
[[1,2],[2,3],[3,4]]
Explanation
The minimum difference is 1.

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 <= 40
  • -1000000 <= arr[i] <= 1000000
  • All elements are distinct.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number[][]}
 */
var minimumAbsDifference = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Absolute Difference — Solution in Python, Java & C++

Minimum Absolute Difference solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Minimum Absolute Difference is an easy coding problem on arrays and sorting, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Arrays, Sorting
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference between them.

Return the pairs in ascending order, each pair written as [a, b] with a < b.

Example 1

Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum difference is 1.

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 <= 40
  • -1000000 <= arr[i] <= 1000000
  • All elements are distinct.

Hints for Minimum Absolute Difference

  1. Hint 1

    After sorting, the minimum difference must occur between adjacent elements.

  2. Hint 2

    One pass finds the minimum gap; a second collects every adjacent pair achieving it.

  3. Hint 3

    Sorting also gives the required output order for free.

How to solve Minimum Absolute Difference

After sorting, the minimum difference occurs between adjacent elements; find it, then collect every adjacent pair achieving it.

Approach

  1. Sort.
  2. Compute the minimum adjacent gap.
  3. Emit [a[i-1], a[i]] for every i with that gap.

Why it works

Any two non-adjacent sorted elements bracket an adjacent pair with a gap no larger, so adjacent pairs suffice; sorted order also yields the required output order.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Values are distinct, so the gap is never zero.

Reference solution

Python

def minimumAbsDifference(arr):
    ordered = sorted(arr)
    best = min(ordered[i] - ordered[i - 1] for i in range(1, len(ordered)))
    return [[ordered[i - 1], ordered[i]] for i in range(1, len(ordered))
            if ordered[i] - ordered[i - 1] == best]

Java

public static int[][] minimumAbsDifference(int[] arr) {
    int[] s = arr.clone();
    Arrays.sort(s);
    int best = s[1] - s[0];
    for (int i = 2; i < s.length; i++) best = Math.min(best, s[i] - s[i - 1]);
    List<int[]> out = new ArrayList<>();
    for (int i = 1; i < s.length; i++) {
        if (s[i] - s[i - 1] == best) out.add(new int[]{s[i - 1], s[i]});
    }
    return out.toArray(new int[0][]);
}

C++

vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
    vector<int> s = arr;
    sort(s.begin(), s.end());
    int best = s[1] - s[0];
    for (int i = 2; i < (int) s.size(); i++) best = min(best, s[i] - s[i - 1]);
    vector<vector<int>> out;
    for (int i = 1; i < (int) s.size(); i++) {
        if (s[i] - s[i - 1] == best) out.push_back(vector<int>{s[i - 1], s[i]});
    }
    return out;
}

JavaScript

var minimumAbsDifference = function(arr) {
    const sorted = arr.slice().sort(function(a, b) { return a - b; });
    let best = Infinity;
    for (let i = 1; i < sorted.length; i++) {
        const d = sorted[i] - sorted[i - 1];
        if (d < best) best = d;
    }
    const out = [];
    for (let i = 1; i < sorted.length; i++) {
        if (sorted[i] - sorted[i - 1] === best) out.push([sorted[i - 1], sorted[i]]);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms