Start learning free

LESSON 202 OF 344 · SORTING

Minimum Absolute Difference in JavaScript: O(n log n) Sort and Scan

Practice O(n log n) Read the full explanation

Given an array of distinct integers nums, 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 nums
  • a < b
  • b - a equals to the minimum absolute difference of any two elements in nums

Example 1:

Input: nums = [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: nums = [1,3,6,10,15]
Output: [[1,3]]

Example 3:

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

Constraints:

  • 2 <= nums.length <= 105
  • -106 <= nums[i] <= 106

STEP 1 OF 9
    Ctrl + Enter to check

    JAVASCRIPT · SORTING

    Minimum Absolute Difference in JavaScript, explained

    Problem overview

    The method minimumAbsDifference receives an array nums of distinct integers. It must return every pair [a, b] with a < b whose difference b - a is the smallest difference found between any two elements. The pairs must be in ascending order.

    For nums = [4, 2, 1, 3] the smallest difference is 1, reached by 1 and 2, 2 and 3, and 3 and 4. The answer is [[1, 2], [2, 3], [3, 4]]. The array can hold up to 100,000 numbers, so checking all pairs, about five billion of them, is too slow.

    Approach: sort, then look only at neighbours

    The brute-force version compares every pair, which costs O(n²). Sorting gives a much faster route, because of one observation: in a sorted array, the closest pair is always made of neighbours.

    Suppose two elements are not adjacent, so some other value m sits between them in the sorted order. Then m is at least as close to each of them as they are to each other, and the pair (smaller, m) has a smaller gap than the pair (smaller, larger). A non-adjacent pair can never reach the minimum, because the elements are distinct and there is always something strictly in between.

    So the plan is: sort ascending, then walk through each neighbouring pair once. Along the way, track the smallest gap and the pairs that reach it. Because the array is sorted, the pairs come out already in ascending order, so no final sort is needed. The cost is the sort, O(n log n), plus a single O(n) scan.

    Take [3, 8, -10, 23, 19, -4, -14, 27]. Sorted, it is [-14, -10, -4, 3, 8, 19, 23, 27]. The neighbour gaps are 4, 6, 7, 5, 11, 4, 4. The smallest is 4, which occurs three times, giving [[-14, -10], [19, 23], [23, 27]].

    Step by step

    1. Sort numerically. Call nums.sort with the comparator (a, b) => a - b. This sorts the caller's array in place.
    2. Seed the record. Declare minDiff as nums[1] - nums[0], the gap of the first neighbouring pair, and minDiffPairs as an empty array. After sorting, the second number is never smaller than the first, so no Math.abs is needed. let is used because a new record replaces the whole array.
    3. Loop over neighbours. Start i at 1 and look back at i - 1, so each iteration handles the pair nums[i - 1] and nums[i].
    4. Compute curDiff as nums[i] - nums[i - 1].
    5. A smaller gap (curDiff < minDiff) beats the record.
    6. Replace the record: assign minDiff = curDiff and make minDiffPairs a new array holding just [nums[i - 1], nums[i]]. Every earlier pair had a larger gap, so it is dropped.
    7. An equal gap is handled by an else if (curDiff === minDiff).
    8. Add the tied pair to the end of minDiffPairs with push.
    9. Return minDiffPairs after the loop.

    The solution in JavaScript

    class Solution {
    minimumAbsDifference(nums) {
        nums.sort((a, b) => a - b);
        let minDiff = nums[1] - nums[0];
        let minDiffPairs = [];
        for (let i = 1; i < nums.length; i++) {
            const curDiff = nums[i] - nums[i - 1];
            if (curDiff < minDiff) {
                minDiff = curDiff;
                minDiffPairs = [[nums[i - 1], nums[i]]];
            } else if (curDiff === minDiff) {
                minDiffPairs.push([nums[i - 1], nums[i]]);
            }
        }
        return minDiffPairs;
    }
}

    The JavaScript details worth a look:

    • The comparator is required. sort() without one compares the elements as strings. For example [10, 9, 1].sort() gives [1, 10, 9]. With (a, b) => a - b the result is numeric and ascending. Subtracting is safe here because the values are small integers.
    • sort changes the input. It reorders the array you pass in. If the caller needs the original order, sort a copy with [...nums].sort(...).
    • Replace versus push. minDiffPairs = [[...]] builds a new array and drops the old contents. push appends to the existing one. The pair itself is a small array created on the spot, so each stored pair is its own object.
    • const inside the loop. A new curDiff is created each time through the body.

    Complexity

    Time: O(n log n). Sorting costs O(n log n) comparisons, and the loop is a single pass of n - 1 constant-time steps. The sort dominates.

    Space: O(n) for the answer in the worst case, when all neighbouring gaps are equal. The sort is done in place on the input array, and only a few variables are added. The engine's sorting routine may use some working memory of its own.

    Edge cases and common mistakes

    • Two elements. [5, 2] sorts to [2, 5] and seeds minDiff with 3. The loop runs once, sees a gap equal to the seed, and pushes [2, 5]. That is why the seed leaves minDiffPairs empty: the loop adds the first pair itself, so it is never added twice.
    • Forgetting the comparator. An array like [10, 9, 1] would be ordered as text, and the neighbours would no longer be the numerically closest.
    • Not clearing on a new record. Pushing a smaller-gap pair onto the old list would leave pairs with the larger gap in the answer.
    • Several pairs at the minimum. Ties are normal: a run like 1, 2, 3, 4 produces three pairs, and the pairs share elements.
    • Using <= in the first test. That would reset the list on a tie and keep only the last tied pair.
    • Negative numbers. They need no special handling, because the comparator and the subtraction work for them.

    Testing

    • [4, 2, 1, 3] gives [[1, 2], [2, 3], [3, 4]].
    • [1, 3, 6, 10, 15] gives [[1, 3]].
    • [3, 8, -10, 23, 19, -4, -14, 27] gives [[-14, -10], [19, 23], [23, 27]].
    • [5, 2] gives [[2, 5]].
    Keep going with JavaScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free