Problem overview
The method minimumAbsDifference receives an array nums of distinct integers. It returns every pair [a, b] with a < b whose difference b - a equals the smallest difference between any two elements. The pairs come back in ascending order.
For [4, 2, 1, 3] the smallest difference is 1 and the answer is [[1, 2], [2, 3], [3, 4]]. For [3, 8, -10, 23, 19, -4, -14, 27] the smallest difference is 4 and the answer is [[-14, -10], [19, 23], [23, 27]].
Approach: after sorting, only neighbours matter
The brute-force solution compares all pairs, which is O(n²). Sorting removes most of that work. In a sorted array, if two elements are not adjacent, there is at least one element between them, and that element is closer to each of them than they are to each other. So the closest pair is always an adjacent pair, and so is every pair that ties for the minimum.
That reduces the problem to one pass over the neighbours. Compute each adjacent difference, keep the smallest one seen so far, and collect the pairs that reach it. There are three cases per neighbour pair: a smaller difference restarts the collection, an equal one is appended, and a larger one is ignored. Sorting costs O(n log n) and the pass costs O(n).
The sorted array also gives each pair as [smaller, larger] and discovers the pairs in ascending order, so no final sort of the pairs is needed. The first lesson on this problem, which uses nested loops, needs both.
Here is the pass on the second example. The sorted array is [-14, -10, -4, 3, 8, 19, 23, 27], and its neighbour gaps are 4, 6, 7, 5, 11, 4 and 4. The first gap, 4, is the starting minimum and its pair [-14, -10] is recorded. Gaps 6, 7, 5 and 11 are larger and change nothing. The last two gaps equal 4, so [19, 23] and [23, 27] are appended. No gap is smaller than 4, so the collection is never restarted.
Step by step
- Sort a copy.
val sorted = nums.sortedis a new ascending array. - Start with the first gap.
minDiffis avarequal tosorted(1) - sorted(0). The statement guarantees two elements. Since the array is sorted, no absolute value is needed.minDiffPairsstarts as an emptyArrayBuffer. - Loop over adjacent pairs with
ifrom 1 untilsorted.length, comparingsorted(i)withsorted(i - 1). - Compute the gap
curDiffassorted(i) - sorted(i - 1). - Check for a new record. If
curDiff < minDiff, earlier pairs no longer qualify. - Restart the collection. Set
minDifftocurDiff, replace the buffer with an empty one and append the pairArray(sorted(i - 1), sorted(i)). - Check for a tie. An
else ifcatchescurDiff == minDiff. - Append the tied pair to the buffer.
- Return the buffer as an array. The method's result type is
Array[Array[Int]].
The solution in Scala
class Solution {
def minimumAbsDifference(nums: Array[Int]): Array[Array[Int]] = {
val sorted = nums.sorted
var minDiff = sorted(1) - sorted(0)
var minDiffPairs = ArrayBuffer[Array[Int]]()
for (i <- 1 until sorted.length) {
val curDiff = sorted(i) - sorted(i - 1)
if (curDiff < minDiff) {
minDiff = curDiff
minDiffPairs = ArrayBuffer[Array[Int]]()
minDiffPairs += Array(sorted(i - 1), sorted(i))
} else if (curDiff == minDiff) {
minDiffPairs += Array(sorted(i - 1), sorted(i))
}
}
return minDiffPairs.toArray
}
}
The Scala details worth knowing:
- Import the buffer class.
ArrayBufferis inscala.collection.mutable, so a standalone file starts withimport scala.collection.mutable.ArrayBuffer. - Type parameters use square brackets.
ArrayBuffer[Array[Int]]()creates an empty buffer whose elements are integer arrays. Array elements are read with parentheses,sorted(i). +=appends to a buffer in place. Thevaris needed only because the restart branch assigns a new buffer to the name.toArrayconverts the buffer to the array the method must return. The elements are the same inner arrays.- The pairs are fresh arrays.
Array(sorted(i - 1), sorted(i))builds a new two-element array each time, so the pairs don't share state withnums. - The local
sortedis a plainvaland doesn't conflict with thesortedmethod used to create it. - Integer range. With values up to a million in size, differences fit in an
Inteasily. Values near the limits ofIntcould overflow the subtraction, which wraps silently in Scala.
Complexity
Time: O(n log n). Sorting is O(n log n) and the loop is a single O(n) pass.
Space: O(n). The sorted copy holds n elements, and the buffer holds at most n - 1 pairs.
Edge cases and common mistakes
- Two elements.
[5, 1]gives[[1, 5]]. The initialminDiffis the gap of that same pair, so the first loop pass sees a tie and appends it. - Several ties. In
[4, 2, 1, 3]all three neighbour gaps equal 1, and all three pairs are kept. - Not resetting on a record. If the new-record branch only appended, pairs from larger gaps would stay in the answer.
- Negative numbers. They need no special handling. Sorting puts them first, and the pairs
[-14, -10]keep the smaller value on the left. - Comparing non-neighbours. In a sorted array it is never needed, because a gap between non-adjacent elements is never smaller than one of the gaps in between.
- Forgetting to sort. On the unsorted
[10, 1, 4], the neighbour gaps are 9 and 3, and the pair[1, 4]would be missed, since 1 and 4 are not neighbours. The adjacent-only check is valid only after sorting.
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, 1, 4]gives[[1, 4]].
