Problem overview
The method minimumAbsDifference receives an array nums of distinct integers. Among all pairs of elements, it must find the smallest absolute difference, then return every pair that reaches it. Each pair is written [a, b] with a < b, and the list of pairs is ordered by its first value.
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] only 1 and 3 are two apart, and every other pair is further, so the answer is [[1, 3]].
Approach: try every pair
This lesson uses the most direct idea. Look at every pair of positions, compute its difference, and keep the best pairs seen so far. With n elements there are about n * (n - 1) / 2 pairs, so the work grows with n². That is fine for small arrays and is a good way to get the logic right. A later lesson on the same problem sorts the array first, because after sorting the closest pair must sit side by side.
The bookkeeping is the interesting part. You track the smallest difference so far, minDiff, and the pairs that achieve it, minDiffPairs. For each new pair there are three cases:
- its difference is smaller than
minDiff: a new record, so every pair collected before is now wrong and gets thrown away; - its difference equals
minDiff: a tie, so the pair is added to the list; - its difference is larger: ignore it.
Step by step
- Start
minDiffwith a real value. Use the difference of the first two elements,abs(nums[0] - nums[1]). A made-up starting value like a huge number would also work, but a real pair needs no special "nothing yet" case. Also createminDiffPairsas an empty[[Int]]. - Loop
iover every position in0..<nums.count. It picks the first element of a pair. - Loop
jover the positions afteri, in(i + 1)..<nums.count. Starting afterimeans each pair is looked at once, and no element is paired with itself. - Compute
curDiffasabs(nums[i] - nums[j]). It is a constant because it never changes inside the iteration. - Handle a new record. If
curDiff < minDiff, updateminDiffand replaceminDiffPairswith a list holding only this pair. - Store the pair in the right order. The array may list the larger number first, so the pair is built as
[min(nums[i], nums[j]), max(nums[i], nums[j])]. - Handle a tie with
else if curDiff == minDiffand append the pair in the same form. - Sort the result after both loops, by each pair's first value, and return it.
The solution in Swift
class Solution {
func minimumAbsDifference(_ nums: [Int]) -> [[Int]] {
var minDiff = abs(nums[0] - nums[1])
var minDiffPairs = [[Int]]()
for i in 0..<nums.count {
for j in (i + 1)..<nums.count {
let curDiff = abs(nums[i] - nums[j])
if curDiff < minDiff {
minDiff = curDiff
minDiffPairs = [[min(nums[i], nums[j]), max(nums[i], nums[j])]]
} else if curDiff == minDiff {
minDiffPairs.append([min(nums[i], nums[j]), max(nums[i], nums[j])])
}
}
}
minDiffPairs.sort { $0[0] < $1[0] }
return minDiffPairs
}
}
The Swift details worth knowing:
- Parameters are constants.
numscan be read but not changed, which is fine here because the function only reads it. The twovardeclarations are the values that change. - Half-open ranges.
0..<nums.countstops beforenums.count. On the last pass of the outer loop,(i + 1)..<nums.countbecomesnums.count..<nums.count, an empty range, so the inner loop just does nothing. A range whose start is above its end, such as3..<2, crashes the program instead. [[Int]]()creates an empty array of integer arrays, andminDiffPairs = [[x, y]]replaces it with an array holding one pair.- The trailing closure.
sort { $0[0] < $1[0] }sorts the array in place.$0and$1are the two pairs being compared, and the closure returnstruewhen the first should come earlier. Comparing only the first values is enough here, because the elements are distinct, so two different pairs never start with the same number. minandmaxare global functions that take two values and return the smaller or larger one.absworks on any signed number. With values this small the subtraction cannot overflow. An overflowingIntsubtraction would crash the program in Swift instead of wrapping around.
Complexity
Time: O(n²) for the loops. The nested loops look at about n * (n - 1) / 2 pairs, and each takes constant time. The final sort of the pairs adds O(k log k), where k is the number of pairs kept, which is at most n - 1, so the loops dominate.
Space: O(k). Only the kept pairs are stored, and there are at most n - 1 of them.
Edge cases and common mistakes
- Not discarding old pairs on a new record. If the record branch appended instead of replacing, pairs with a larger difference would stay in the answer. For
[4, 2, 1, 3]the first pair seen is 4 and 2, with difference 2, and it must disappear once a difference of 1 appears. - Skipping the final sort. The pairs are collected in the order the loops find them. For
[4, 2, 1, 3]that order is[[3, 4], [1, 2], [2, 3]], which is not ascending. - Starting
jati. The pair of an element with itself has difference 0, which would always win. - Forgetting
minandmax. For the pair 4 and 3 the loops meet 4 first, so[nums[i], nums[j]]would give[4, 3]where[3, 4]is wanted. - Fewer than two elements.
nums[1]doesn't exist for an array of one element, and reading it crashes. The lesson guarantees at least two elements.
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]].
