Problem overview
The function minimumAbsDifference(nums []int) [][]int receives a slice of distinct integers. It must find the smallest absolute difference between any two elements, then return every pair [a, b] with a < b and b - a equal to that smallest difference. The pairs are returned in ascending order.
For nums = [4, 2, 1, 3] the smallest difference is 1, and the pairs are [[1 2] [2 3] [3 4]]. For [1, 3, 6, 10, 15] it is 2, and the only pair is [[1 3]]. For [3, 8, -10, 23, 19, -4, -14, 27] it is 4, giving [[-14 -10] [19 23] [23 27]].
The input has at least two elements, so a first pair always exists.
Approach: compare every pair, keep the best ones
The brute force looks at every pair of positions (i, j) with j > i and computes the absolute difference. It maintains two things: the smallest difference seen so far, minDiff, and the list of pairs that reach it, minDiffPairs.
- If the current difference is smaller than
minDiff, there is a new record. All collected pairs are now wrong, so the list is replaced by one that holds only the current pair. - If it equals
minDiff, the pair ties the record and is appended. - If it is larger, the pair is ignored.
Each pair is stored as [smaller, larger] because the input can list the two values in either order. At the end, the list is sorted so the output order does not depend on the input order.
There are n(n-1)/2 pairs, so the time is O(n^2). A sorted-array solution is faster and comes in a later lesson; this one needs no sorting during the search.
Step by step
- Initialize
minDiffwithabs(nums[0] - nums[1]), the difference of the first pair. Go has no built-in integer absolute value, so the lesson provides anabshelper. Starting from a real difference avoids an artificial "no value yet" sentinel. - Initialize
minDiffPairsas an empty[][]int:[][]int{}. - Write the outer loop over
ifor the first element of each pair. - Write the inner loop over
jstarting ati + 1, so each pair is visited once and an element is never paired with itself. - Compute
curDiffasabs(nums[i] - nums[j]). - New record. If
curDiff < minDiff, setminDifftocurDiffand replaceminDiffPairswith a slice of one pair, usingminandmaxso the smaller value comes first. - Tie. Otherwise, if
curDiff == minDiff, append the pair[]int{min(...), max(...)}. - Sort the pairs with
sort.Sliceby the first element. The less function receives positions in the slice, not the elements, so it indexes back intominDiffPairs. - Return
minDiffPairs.
The solution in Go
func minimumAbsDifference(nums []int) [][]int {
minDiff := abs(nums[0] - nums[1])
minDiffPairs := [][]int{}
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
curDiff := abs(nums[i] - nums[j])
if curDiff < minDiff {
minDiff = curDiff
minDiffPairs = [][]int{{min(nums[i], nums[j]), max(nums[i], nums[j])}}
} else if curDiff == minDiff {
minDiffPairs = append(minDiffPairs, []int{min(nums[i], nums[j]), max(nums[i], nums[j])})
}
}
}
sort.Slice(minDiffPairs, func(a, b int) bool { return minDiffPairs[a][0] < minDiffPairs[b][0] })
return minDiffPairs
}Go details:
- Composite literals. In
[][]int{{x, y}}the inner type may be left out, so{x, y}stands for[]int{x, y}. Theappendline writes the type out becauseappendtakes a single element, not a literal in braces. minandmaxare built-in functions since Go 1.21, so they need no import.absis not built in. The math package hasmath.Abs, but it works onfloat64, which is why an integer helper is used.- Resetting the list. Assigning a new slice to
minDiffPairsdrops the old pairs. Because the old backing array is no longer referenced, it can be garbage collected. - Sorting by the first element only is enough here. Every pair in the list has the same difference
d, so a pair is determined by its first element:[a, a+d]. Two different pairs therefore never share a first element, and the comparison never ties. sort.Sliceis not stable, but with all keys different, stability does not matter.
Complexity
Time: O(n^2). The loops visit n(n-1)/2 pairs, each in constant time. Sorting the answer adds O(k log k) for k result pairs, and since k < n, this is dominated by the loops.
Space: O(1) extra, not counting the returned list. The list itself holds at most n - 1 pairs. Pairs that were collected and then discarded on a new record can be reclaimed.
The brute force suits small inputs. With a length near 100,000, it would need about five billion pair checks, which is why the later lesson sorts the slice first.
Edge cases and common mistakes
- Two elements.
[5, 1]gives[[1 5]]. The initialminDiffalready comes from this pair, and the loop finds it as a tie. - Input order.
[10, 1]returns[[1 10]]: the smaller value is always first, whichever way the input lists them. - Forgetting to clear the list. If a new record only changed
minDiffbut kept the old pairs, the result would include pairs with a larger difference. - Using
<=for the record test. That would reset the list on every tie and keep only the last pair. - Skipping the sort. The pairs are found in input order, so for
[4, 2, 1, 3]the result would come out unsorted. - Negative numbers. They need no special handling, as the absolute value takes care of the sign.
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]].