Problem overview
The method minimumAbsDifference receives an array nums of distinct integers and must return every pair [a, b] with a < b whose gap b - a is the smallest gap between any two elements. The pairs come back in ascending order.
For nums = [4, 2, 1, 3] the smallest gap is 1, reached by 1 and 2, 2 and 3, and 3 and 4. The answer is [[1, 2], [2, 3], [3, 4]]. For [3, 8, -10, 23, 19, -4, -14, 27] the smallest gap is 4, and the answer is [[-14, -10], [19, 23], [23, 27]].
Approach: sort, then compare neighbours
Checking every pair costs O(n²). Sorting removes the need. In a sorted array, if two values are not next to each other, there is a third value between them, and both of its gaps are smaller than the gap across the pair. So a pair that isn't adjacent can never have the smallest gap. Only the n - 1 neighbouring pairs matter.
A second benefit: the neighbouring pairs come out in ascending order by themselves, and each one already has its smaller value first. That removes both the min/max handling and the final sort of the brute-force version.
The loop then follows the same three cases as before. A smaller gap replaces the collected pairs, an equal gap adds a pair, and a larger gap is ignored.
A worked example
Take [3, 8, -10, 23, 19, -4, -14, 27]. Sorted, it is [-14, -10, -4, 3, 8, 19, 23, 27]. The neighbouring gaps are 4, 6, 7, 5, 11, 4 and 4. The seed is 4, taken from the first pair. The pair -14 and -10 is appended on the first iteration, because its gap ties with the seed. The gaps 6, 7, 5 and 11 are larger and are ignored. The pairs 19 and 23, and 23 and 27, both tie with 4 and are appended. No gap was smaller than 4, so nothing was ever discarded, and the result is [[-14, -10], [19, 23], [23, 27]].
The same scan on [1, 3, 6, 10, 15] sees gaps 2, 3, 4 and 5 and keeps only the first pair.
Step by step
- Sort into a new array. The parameter is a constant, so
nums.sorted()returns a sorted copy, stored insortedNums. - Seed the record.
minDiffstarts as the gap between the first two sorted values,sortedNums[1] - sortedNums[0]. Noabsis needed, since sorted neighbours are never negative apart.minDiffPairsstarts as an empty[[Int]]. - Loop
ifrom 1 up tosortedNums.count, so each iteration looks at the pair at positionsi - 1andi. - Compute
curDiffassortedNums[i] - sortedNums[i - 1]. - New record: if
curDiff < minDiff, store it inminDiffand replaceminDiffPairswith a list holding just this pair. - Tie: with
else if curDiff == minDiff, append the pair. - Return
minDiffPairsafter the loop.
The first pair, at i = 1, ties with the seeded minDiff and is appended, so it is included without a special case.
The solution in Swift
class Solution {
func minimumAbsDifference(_ nums: [Int]) -> [[Int]] {
let sortedNums = nums.sorted()
var minDiff = sortedNums[1] - sortedNums[0]
var minDiffPairs = [[Int]]()
for i in 1..<sortedNums.count {
let curDiff = sortedNums[i] - sortedNums[i - 1]
if curDiff < minDiff {
minDiff = curDiff
minDiffPairs = [[sortedNums[i - 1], sortedNums[i]]]
} else if curDiff == minDiff {
minDiffPairs.append([sortedNums[i - 1], sortedNums[i]])
}
}
return minDiffPairs
}
}
The Swift details worth knowing:
sorted()versussort().sorted()returns a new array and leavesnumsalone.sort()sorts in place and needs avar, which a parameter isn't.- The range
1..<sortedNums.count. It is empty when the array has exactly one element, and the loop is skipped. Before that, though,sortedNums[1]is read forminDiff, and with fewer than two elements that read crashes. The lesson guarantees at least two. - Nested array literals.
[[sortedNums[i - 1], sortedNums[i]]]is an array containing one two-element array. Arrays are values in Swift, so appending a pair copies it intominDiffPairs. - No overflow here.
Intis 64 bits in Swift, and an overflowing subtraction would crash the program instead of wrapping. With values of at most a million in size, the gaps are tiny compared to that limit.
Complexity
Time: O(n log n). Sorting costs O(n log n) and the loop is one pass of O(n), so sorting dominates. This is a clear gain over the O(n²) version.
Space: O(n). The sorted copy holds n values, and the result holds up to n - 1 pairs.
Edge cases and common mistakes
- Two elements.
[5, 2]sorts to[2, 5], the loop runs once and ties with the seed, and the answer is[[2, 5]]. - Several pairs tied. A sorted
[1, 2, 3, 4]gives all three neighbouring pairs, since each gap is 1. - A record that shows up late. For
[1, 3, 6, 10, 15]the early gap is 2, and no later gap is smaller, so the answer is[[1, 3]]. If a smaller gap appears later, the old pairs must be dropped, which is what the replacement in the first branch does. - Looping to the wrong end. Using
1...sortedNums.countreads one position past the end and crashes. The half-open range stops at the last valid index. - Comparing across non-neighbours. Checking
sortedNums[i + 1]or other positions adds work and gains nothing.
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]].
