Problem overview
The method minimumAbsDifference receives an array nums of distinct integers. Look at every pair of elements and find the smallest absolute difference between any two of them. Then return every pair whose difference equals that smallest value. Each pair is written [a, b] with a < b, and the list of pairs is sorted in ascending order.
For nums = [4, 2, 1, 3] the smallest difference is 1. The pairs that reach it are 1 and 2, 2 and 3, and 3 and 4, so the answer is [[1, 2], [2, 3], [3, 4]]. For [1, 3, 6, 10, 15] the smallest gap is 2, between 1 and 3 only, so the answer is [[1, 3]].
Approach: compare every pair, keep the best
The direct idea needs no cleverness. Compare each element with every element after it, and keep track of the smallest difference seen so far together with the pairs that reached it. For each new pair there are three outcomes:
- Its difference is smaller than the record. The old pairs no longer matter, so start a new list holding only this pair.
- Its difference equals the record. Add the pair to the list.
- Its difference is larger. Ignore it.
When all pairs have been seen, the list holds every pair at the minimum. The pairs were found in loop order, not sorted order, so the last job is to sort the list.
With n elements there are about n * (n - 1) / 2 pairs, so this takes O(n²) time. That is fine for a small array and the right starting point for a Nested Loops chapter. It is too slow for the largest inputs the statement allows, 100,000 elements. The faster approach sorts first and compares only neighbours, as the sorting version of this problem shows.
Step by step
- Seed the record. Set
minDiffto the absolute difference of the first two elements, andminDiffPairsto an empty array. Starting from a real difference means no "infinity" placeholder is needed. The statement promises at least two elements. - Outer loop with
i. It picks the first element of each pair. - Inner loop with
jstarting ati + 1. Starting afteriavoids pairing an element with itself and avoids visiting the same pair twice in reverse order. - Compute
curDiffwithMath.abs(nums[i] - nums[j]). The absolute value is used because either element may be the larger one. - Smaller than the record? Check
curDiff < minDiff. A new record makes everything collected so far obsolete. - Replace the record. Assign
minDiff = curDiffand makeminDiffPairsa fresh array holding just this pair. The pair is written[Math.min(...), Math.max(...)]so the smaller number always comes first, whichever index it had. - Equal to the record? An
else iftestscurDiff === minDiff. - Add the tied pair with
push, again as smaller then larger. - Sort and return. After both loops, sort
minDiffPairsby the first element of each pair and return it.
The solution in JavaScript
class Solution {
minimumAbsDifference(nums) {
let minDiff = Math.abs(nums[0] - nums[1]);
let minDiffPairs = [];
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
const curDiff = 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;
}
}
The JavaScript details worth a look:
letandconst.minDiffPairsis declared withletbecause a new record replaces the whole array.curDiffis aconst, since it is set once per pair. Each iteration gets a fresh binding.- Mutating versus replacing.
pushchanges the existing array. Assigning a new array literal discards the old contents in one step. ===. Comparing two numbers with===is the standard choice. It never converts types.- The sort comparator. Called without an argument,
sort()converts elements to strings and compares them, which would compare the arrays[1, 2]and[10, 11]as the text"1,2"and"10,11". Here the comparator(a, b) => a[0] - b[0]returns a negative number, zero or a positive number, and compares real numbers.sortworks in place and also returns the array. - Sorting by the first element is enough. The elements are distinct, and all pairs share the same difference. Two pairs with the same first element would need the same second element, so they would be one pair.
Complexity
Time: O(n²). The two loops visit about n² / 2 pairs, and each visit does constant work. The final sort handles at most n - 1 pairs, since the pairs at the minimum difference form a chain through the sorted values, so its O(n log n) cost is dominated by the loops.
Space: O(n) for the result in the worst case, where every neighbouring pair ties. Beyond the result, the extra memory is a few variables.
Edge cases and common mistakes
- Exactly two elements.
[5, 2]has one pair. The seed already holds its difference, 3, butminDiffPairsstarts empty, and the first comparison findscurDiff === minDiffand pushes[2, 5]. That is why theelse ifbranch matters. - Forgetting to clear on a new record. If a smaller difference only pushed the pair, the old, larger-gap pairs would stay in the answer.
- Not ordering each pair. Writing
[nums[i], nums[j]]would produce[4, 2]when the larger number comes first in the input. - Sorting without a comparator. The default sort compares text, so for pairs like
[10, 11]and[2, 3]the order would be wrong:"10,11"comes before"2,3"as text. - Negative numbers. They are fine. In
[3, 8, -10, 23, 19, -4, -14, 27]the gap between -14 and -10 is 4, which ties with 19 and 23, and 23 and 27.
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]].