Problem overview
The method minimumAbsDifference receives a list nums of distinct integers. Among all pairs of elements, find the smallest absolute difference. Then return every pair whose difference equals that minimum. Each pair is written [a, b] with a < b, and the list of pairs is in ascending order.
For nums = [4, 2, 1, 3], the smallest gap between any two numbers is 1. The pairs with that gap are 1 and 2, 2 and 3, 3 and 4, so the answer is [[1, 2], [2, 3], [3, 4]]. For [1, 3, 6, 10, 15] only 1 and 3 are 2 apart, and no other pair is that close, so the answer is [[1, 3]].
Approach: look at every pair
This chapter is about nested loops, so the lesson takes the direct route. Compare every element with every element after it, track the smallest difference seen so far, and keep the pairs that reach it.
Keeping the pairs needs one rule. When a pair has a smaller difference than the current record, everything collected so far is out of date, so the list is replaced by a new list holding just that pair. When a pair ties with the record, it is added to the list.
The cost is quadratic: a list of n numbers has about n * (n - 1) / 2 pairs. That is fine for small inputs. A later lesson on the same problem sorts the list first, so the closest pairs are neighbours, and checks only n - 1 pairs.
Step by step
- Start the record with the first pair.
minDiffbegins asabs(nums[0] - nums[1]). A real difference as a starting value avoids a special "nothing yet" value.minDiffPairsstarts as an empty list. - Loop over the first element of each pair with
i. - Loop over the second element with
j, starting ati + 1. Starting there means each pair is visited once, and an element is never paired with itself. - Compute
curDiffasabs(nums[i] - nums[j]). The input isn't sorted, so either element can be the larger, andabsremoves the sign. - If
curDiff < minDiff, a new record has been found. - Replace the record and the list. Set
minDifftocurDiff, and setminDiffPairsto a new list with one pair. The pair is written smaller value first usingminandmax, becausenums[i]may be the larger one. - Otherwise, if
curDiff == minDiff, the pair ties with the record. - Add the tied pair to
minDiffPairs, again as[min, max]. - Return
sorted(minDiffPairs). Pairs are found in the order the loops visit them, which isn't the required ascending order.
The solution in Python
class Solution:
def minimumAbsDifference(self, nums: List[int]) -> List[List[int]]:
minDiff = abs(nums[0] - nums[1])
minDiffPairs = []
for i in range(0, len(nums)):
for j in range(i + 1, len(nums)):
curDiff = abs(nums[i] - nums[j])
if curDiff < minDiff:
minDiff = curDiff
minDiffPairs = [[min(nums[i], nums[j]), max(nums[i], nums[j])]]
elif curDiff == minDiff:
minDiffPairs.append([min(nums[i], nums[j]), max(nums[i], nums[j])])
return sorted(minDiffPairs)
Python details worth a look:
- Replacing, not clearing. The new-record branch assigns a fresh list instead of changing the old one. The old list is simply dropped.
- Sorting lists of lists. Python compares two lists element by element, so
sortedorders the pairs by the first number and uses the second to break ties. For example,sorted([[3, 4], [1, 2], [1, 0]])gives[[1, 0], [1, 2], [3, 4]]. sortedreturns a new list. It doesn't changeminDiffPairs, which is why its result is returned directly.list.sort()would sort in place and returnNone.range(i + 1, len(nums))is empty wheniis the last index, so the inner loop does nothing on the final pass of the outer one.
Complexity
Time: O(n²). The two loops visit about n * (n - 1) / 2 pairs, and each visit does constant work. Sorting the answer adds O(m log m) for m result pairs, and m is smaller than n because distinct numbers can give at most n - 1 closest pairs. This is only practical for small lists. With the upper limit of 100,000 numbers in the statement, the pair count would be around five billion, which is why the sorting approach exists.
Space: O(m) for the list of pairs, where m is the number of closest pairs. Nothing else grows with the input.
Edge cases and common mistakes
- Two elements.
[5, 1]returns[[1, 5]]. The inner loop runs once, and the pair is written smaller first. - Negative numbers. The difference is taken with
abs, so[-14, -10]has gap 4. The pair is written[-14, -10], since -14 is smaller. - Several ties. In
[4, 2, 1, 3]the first pair visited is 4 and 2 with gap 2. Later pairs with gap 1 replace it, then tie with each other and are appended. The order of discovery differs from the final order, so the lastsortedis needed. - Forgetting to reset the list. If a smaller gap is found and the old pairs aren't discarded, the result includes pairs that aren't the closest.
- Skipping
minandmax. Writing[nums[i], nums[j]]gives pairs like[4, 2]when the earlier element is larger. - Starting
jati. That pairs each element with itself, a gap of 0, which would then win every time.
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]].