Problem overview
The method minimumAbsDifference receives an array nums of distinct integers. It must find the smallest absolute difference between any two elements, then return every pair of elements that differ by exactly that amount. Each pair is written [a, b] with a < b, and the pairs come back in ascending order.
For nums = [4, 2, 1, 3], the smallest difference is 1. The pairs that reach it are [1, 2], [2, 3] and [3, 4]. For [3, 8, -10, 23, 19, -4, -14, 27] the smallest difference is 4, and three pairs reach it: [-14, -10], [19, 23] and [23, 27].
Approach: check every pair
This chapter is about nested loops, so the idea is the direct one. Take every pair of positions (i, j) with i < j, compute the absolute difference of the two values, and keep track of the best difference seen so far together with the pairs that reached it.
For each new difference there are three cases:
- It is smaller than the best so far. Every pair collected up to now is out of the running, so the list restarts with this one pair.
- It equals the best so far. The pair is added to the list.
- It is larger. Nothing happens.
Looping over j from i + 1 visits each unordered pair exactly once. The pairs are discovered in the order of their positions in nums, not their values, so the list is sorted at the end.
The cost is O(n²) comparisons, which is fine for the small arrays that teach the pattern. The constraints allow up to 100,000 elements, which would mean about five billion pairs. The next lesson on this problem sorts first and compares only neighbours, a much faster route.
Step by step
- Start the best difference with a real value.
minDiffbegins as the difference between the first two elements. The statement guarantees at least two elements, so there is always a first pair to compare, and no "infinity" placeholder is needed. - Create an empty collection for the pairs. It is an
ArrayBuffer, a growable array, because the number of pairs isn't known in advance. - Loop over the first element of every pair with
ifrom0 until nums.length. - Loop over the second element with
jfrom(i + 1) until nums.length, so no pair is repeated and no element is paired with itself. - Compute the difference
curDiffas the absolute value ofnums(i) - nums(j). - On a new record (
curDiff < minDiff), store the newminDiffand replace the buffer with a new one holding only this pair. - Write the pair as smaller first. Either element might be the smaller one, so
Math.minandMath.maxput them in the required order. - On a tie (
curDiff == minDiff), append the pair to the buffer. - Sort the pairs by their first element, so the output order doesn't depend on the order of the input.
- 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]] = {
var minDiff = Math.abs(nums(0) - nums(1))
var minDiffPairs = ArrayBuffer[Array[Int]]()
for (i <- 0 until nums.length) {
for (j <- (i + 1) until nums.length) {
val curDiff = Math.abs(nums(i) - nums(j))
if (curDiff < minDiff) {
minDiff = curDiff
minDiffPairs = ArrayBuffer(Array(Math.min(nums(i), nums(j)), Math.max(nums(i), nums(j))))
} else if (curDiff == minDiff) {
minDiffPairs += Array(Math.min(nums(i), nums(j)), Math.max(nums(i), nums(j)))
}
}
}
minDiffPairs = minDiffPairs.sortBy(pair => pair(0))
minDiffPairs.toArray
}
}
The Scala details worth knowing:
ArrayBuffermust be imported. It lives inscala.collection.mutable, so a standalone file needsimport scala.collection.mutable.ArrayBufferat the top.varfor values that change.minDiffandminDiffPairsare reassigned inside the loops, so they arevar.curDiffnever changes after it is computed, so it is aval.- Indexing uses parentheses. An array element is
nums(i), notnums[i]. Square brackets in Scala hold type parameters, as inArrayBuffer[Array[Int]]. for (i <- 0 until n)loops over0ton - 1. The range excludes its end, while0 to nwould includenand read past the array.+=on a buffer appends. On avalorvarholding anArrayBuffer,buffer += xaddsxto the same buffer. That is different fromminDiff = curDiff, which rebinds a variable.sortByreturns a new buffer. It doesn't sort in place, so the result is assigned back tominDiffPairs. It sorts by the key the lambda returns, here the first element of each pair.- The last expression is the result.
minDiffPairs.toArrayhas noreturnin front of it, and none is needed.
Complexity
Time: O(n²). The two loops visit n(n - 1)/2 pairs, each in constant time. The final sort costs O(k log k) for k tied pairs. Since k is below n, the quadratic part dominates.
Space: O(k) for the buffer of k pairs, which is at most n - 1 because the values are distinct.
Edge cases and common mistakes
- Only two elements.
[5, 1]gives[[1, 5]]. The initialminDiffis the difference of that same pair, so when the loops reach it,curDiff == minDiffand theelse ifbranch adds it. The first pair is always recorded this way unless a smaller difference replaces it. - Forgetting to reset on a record. If the new-record branch only updated
minDiffand appended, the buffer would keep pairs from larger differences. - Writing the pair in input order. For
[10, 1, 4]the pair of 4 and 1 must be written[1, 4], not[4, 1]. - Starting
jati. An element paired with itself has difference 0, which would beat every real pair. - Skipping the sort. The pairs are found in input order. For
[4, 2, 1, 3]the buffer ends up as[3, 4],[1, 2],[2, 3], which only becomes the required ascending order aftersortBy.
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]].
