Start learning free

LESSON 198 OF 348 · NESTED LOOPS & BRUTE FORCE

Minimum Absolute Difference in TypeScript: O(n^2) Pair Scan

Practice O(n2) 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 10
    Ctrl + Enter to check

    TYPESCRIPT · NESTED LOOPS & BRUTE FORCE

    Minimum Absolute Difference in TypeScript, explained

    Problem overview

    The method minimumAbsDifference receives an array of distinct integers, nums. Among all pairs of elements, find the smallest absolute difference, then return every pair that achieves it. Each pair is written [a, b] with a < b, and the list of pairs is in ascending order.

    For nums = [4, 2, 1, 3] the smallest difference is 1, reached by 1 and 2, by 2 and 3, and by 3 and 4. The answer is [[1, 2], [2, 3], [3, 4]]. For [1, 3, 6, 10, 15] only 1 and 3 are 2 apart and nothing is closer, so the answer is [[1, 3]]. For [3, 8, -10, 23, 19, -4, -14, 27] the smallest difference is 4, and three pairs have it: [[-14, -10], [19, 23], [23, 27]].

    Approach: look at every pair, keep the best

    The lesson takes the direct route. Look at every pair of elements and compute the absolute difference. Keep two things as you go: the smallest difference seen so far, minDiff, and the list of pairs that reach it, minDiffPairs. For each new pair there are three cases:

    • Its difference is smaller than minDiff. This is a new record, so every pair collected so far is now worse. Replace the list with just this pair.
    • Its difference equals minDiff. It ties the record, so add it to the list.
    • Its difference is larger. Ignore it.

    The pairs are discovered in index order, not in sorted order, and each pair may be found as (larger, smaller). So the code writes every pair as the smaller value first, then sorts the list at the end. With about n^2 / 2 pairs examined, the running time is O(n^2). A faster idea is to sort the numbers first, since the closest pairs must be neighbours in sorted order. This lesson practises the pair scan instead.

    Step by step

    1. Set the starting record. Declare minDiff with let, typed number, as Math.abs(nums[0] - nums[1]), the difference of the first pair. Starting from a real difference avoids a made-up "no value yet" sentinel such as Infinity. Declare minDiffPairs as an empty number[][].
    2. Pick the first element. The outer loop variable i runs over all indexes.
    3. Pick the second element. The inner loop variable j starts at i + 1, so each pair is visited once and never pairs an element with itself.
    4. Measure the pair. Declare curDiff as a const equal to Math.abs(nums[i] - nums[j]).
    5. Handle a new record. If curDiff < minDiff, set minDiff to curDiff and replace minDiffPairs with a new array holding only this pair, written as [Math.min(nums[i], nums[j]), Math.max(nums[i], nums[j])]. The min and max put the smaller number first regardless of where the two elements sit in the input.
    6. Handle a tie. Add an else if for curDiff === minDiff that pushes the same kind of pair onto minDiffPairs.
    7. Sort the result. After both loops, sort minDiffPairs in place with a comparator that orders two pairs a and b by their first element.
    8. Return minDiffPairs.

    The solution in TypeScript

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

    Details worth knowing:

    • The first pair is counted. minDiff starts as the difference of nums[0] and nums[1], but minDiffPairs starts empty. When the loops reach the pair at indexes 0 and 1, its difference equals minDiff, so the tie branch adds it. It is neither lost nor added twice.
    • The comparator must return a number. sort with no comparator turns the elements into strings and compares those. For pairs that would compare "10,1" and "9,2" as text, and [10, 1] would come before [9, 2]. The comparator (a, b) => a[0] - b[0] returns a negative number, zero or a positive number, and compares the first elements as numbers.
    • Sorting by the first element is enough. The values are distinct, and every pair in the list has the same difference, so no two pairs can start with the same value. There are no ties for the comparator to break.
    • Arrays inside arrays. number[][] is an array of number[]. Pushing [a, b] adds one new inner array, and the replacement [[...]] in the record branch has two pairs of brackets: the outer array and the single pair inside it.
    • Reassigning the list is deliberate. In the record branch, minDiffPairs is set to a new array instead of being emptied. The variable is declared with let so that this works.

    Complexity

    Let n be the length of nums.

    Time: O(n^2). The two loops examine n(n - 1) / 2 pairs, each in constant time. The final sort takes O(k log k) for k pairs in the list, and k is below n, because each element takes part in at most two minimum pairs. This is much smaller than the pair scan.

    Space: O(k) beyond the input, for the list of result pairs, which is at most n - 1 pairs.

    The quadratic scan is fine for a few thousand elements. It is too slow for very large arrays: a hundred thousand elements means about five billion pair checks.

    Edge cases and common mistakes

    • Exactly two elements. [5, 1] gives [[1, 5]]. The pair is written smaller first even though 5 comes first in the input.
    • Reading nums[1] with too few elements. The lesson guarantees at least two numbers. With one element, nums[1] is undefined and the difference is NaN.
    • Forgetting to reset on a new record. If the list is never replaced, pairs from an earlier, larger difference stay in the result.
    • Using <= in the first test. A tie would then replace the list instead of adding to it, and only the last tied pair would survive.
    • Not normalising the pair. Without Math.min and Math.max, a pair like [4, 3] could appear when the larger value sits earlier in the input.
    • Sorting without a comparator. The default sort compares as text, so negative numbers and numbers with different digit counts come out in the wrong order.
    • Comparing the wrong difference. Without Math.abs, a pair like nums[i] - nums[j] could be negative and look like a better record than it is.

    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]].
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free