Start learning free

LESSON 206 OF 348 · SORTING

Minimum Absolute Difference in TypeScript: Sort and Compare Neighbours

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

    TYPESCRIPT · SORTING

    Minimum Absolute Difference in TypeScript, explained

    Problem overview

    The method minimumAbsDifference receives an array of distinct integers, nums. It must find the smallest difference between any two elements and return every pair [a, b] that reaches it, with a < b. The pairs must be listed in ascending order.

    In the first example, [4, 2, 1, 3], the closest values differ by 1, and three pairs do it: [1, 2], [2, 3] and [3, 4]. In the second example, [1, 3, 6, 10, 15], the smallest gap is 2 and only [1, 3] has it. In the third, [3, 8, -10, 23, 19, -4, -14, 27], the smallest gap is 4, shared by [-14, -10], [19, 23] and [23, 27].

    The array has between 2 and 100,000 elements, each between -1,000,000 and 1,000,000. Checking every pair would take about n² comparisons, which is too many for 100,000 elements.

    Approach: sort, then look only at neighbours

    After sorting in ascending order, the closest pair is always made of two elements that are next to each other. Suppose two elements are further apart in the sorted array, with some value between them. That middle value forms a pair with each of them, and both gaps are smaller than the whole distance. So no pair with elements in between can be the closest.

    That reduces the work to the n - 1 adjacent pairs. Walk through them once, track the smallest gap seen so far, and keep the list of pairs that have that gap. When a smaller gap appears, throw the list away and start a new one; when an equal gap appears, add to the list. A bonus of sorting is that the pairs are discovered in ascending order, as the statement requires.

    For the first example, the sorted array is [1, 2, 3, 4]. The first gap is 1, so minDiff is 1 and the list starts empty. Index 1 gives gap 1, which equals minDiff, so [1, 2] is added. Index 2 adds [2, 3] and index 3 adds [3, 4].

    Step by step

    1. Sort nums with the comparator (a, b) => a - b. Without it, numbers are compared as strings, and the neighbours in that order are not the closest numbers.
    2. Start minDiff with the first gap, nums[1] - nums[0], and create minDiffPairs as an empty number[][]. Both use let because they are reassigned.
    3. Loop over the adjacent pairs, with i starting at 1.
    4. Compute the current gap as const curDiff = nums[i] - nums[i - 1].
    5. If curDiff < minDiff, this gap is a new record.
    6. Replace the record. Set minDiff to curDiff and make minDiffPairs a new array holding only [nums[i - 1], nums[i]].
    7. Otherwise, if curDiff === minDiff, the gap ties the record.
    8. Add the tie: push [nums[i - 1], nums[i]] onto minDiffPairs.
    9. Return minDiffPairs after the loop.

    The loop starts at index 1, so the very first gap is looked at again. It is equal to minDiff, so it is pushed on that pass. That's why the list can begin empty.

    The solution in TypeScript

    class Solution {
    minimumAbsDifference(nums: number[]): number[][] {
        nums.sort((a, b) => a - b);
        let minDiff = nums[1] - nums[0];
        let minDiffPairs: number[][] = [];
        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;
    }
}

    Details worth knowing:

    • A nested array literal. [[nums[i - 1], nums[i]]] is an array holding one pair. The outer brackets are the list, the inner ones are the pair, and the declared type number[][] matches.
    • Replace, don't clear. Assigning a fresh array to minDiffPairs is safe here because nobody else holds the old list.
    • const inside a loop. Each pass makes a new curDiff, so const is fine.
    • The comparator is required. The default sort() would turn [10, 9, 100, 11] into [10, 100, 11, 9].
    • The sort changes the caller's array, and returns pairs as new arrays.

    Complexity

    Time: O(n log n). The sort takes O(n log n), and the loop is a single pass.

    Space: O(1) besides the output. Only a few variables are used. The returned list of pairs can hold up to n - 1 pairs, which is the answer itself. When the sort runs in place, no copy of the input is made.

    Edge cases and common mistakes

    • Two elements. [5, 1] gives [[1, 5]]. The smaller value comes first in the pair.
    • Every gap equal. [1, 2, 3, 4] returns all three adjacent pairs.
    • Negative values. Differences of sorted neighbours are never negative, so the sign of the numbers doesn't matter.
    • Comparing every pair. It gives the right answer but takes O(n²) time, which is too slow at 100,000 elements.
    • Using <= instead of < in the first test. Then a tie would reset the list instead of extending it, and the earlier pairs would be lost.
    • Forgetting the reset on a new record. Pairs with a larger gap would stay in the answer.
    • Distinct values. The statement guarantees no duplicates. With duplicates, the minimum gap would be 0 and the condition a < b would no longer fit.

    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, 1] gives [[1, 5]].
    • [10, 9, 100, 11] gives [[9, 10], [10, 11]].
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free