Problem overview
The method minimumAbsDifference receives an array nums of distinct integers. It must find the smallest absolute difference between any two elements and return every pair [a, b] with a < b whose difference b - a equals that smallest value. The pairs come back 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] the answer is [[1, 3]].
Approach: sort, then compare neighbours
The brute-force way checks every pair of elements, which is O(n²). With up to 100,000 elements, that is far too slow. Sorting removes the need for it.
In a sorted array, take any two elements that are not neighbours, say at positions p and q with something between them. The element in between lies within that range, so it forms a pair with each of them that has a strictly smaller gap. A pair that is not adjacent therefore can never have the minimum difference. Only neighbouring elements need to be compared, which takes one pass.
Sorting also solves the output order. The adjacent pairs, read left to right, already come out as ascending [a, b] with a < b, so no extra sort of the result is needed.
On [4, 2, 1, 3], sorting gives [1, 2, 3, 4]. The neighbour gaps are 1, 1 and 1, all equal to the minimum, so all three pairs are returned.
A longer trace shows the reset. Take [3, 8, -10, 23, 19, -4, -14, 27], which sorts to [-14, -10, -4, 3, 8, 19, 23, 27]. The neighbour gaps are 4, 6, 7, 5, 11, 4 and 4. The loop starts with minDiff = 4, and the first pair [-14, -10] is added as a tie. The gaps 6, 7, 5 and 11 are all larger and are ignored. The last two gaps equal 4, so [19, 23] and [23, 27] are appended. No gap was smaller than 4, so the list was never reset.
The first lesson on this problem solves it with two nested loops. The idea there is the same, keep the best gap and reset on a new record, but it examines every pair and has to sort the result at the end. Sorting the input first turns n²/2 comparisons into n - 1.
Step by step
- Sort the array in place with
Arrays.sort(nums). - Start the best gap at the first adjacent difference,
nums[1] - nums[0], and create an emptyList<List<Integer>>namedminDiffPairs. In a sorted array the later number is never smaller, so noMath.absis needed. - Loop over the neighbours with
istarting at 1, so each step looks at the pairnums[i - 1]andnums[i]. - Compute the gap as
curDiff, equal tonums[i] - nums[i - 1]. - Test for a new record with
curDiff < minDiff. - On a record, reset. Update
minDiff, replace the list with a new empty one, and add the pairArrays.asList(nums[i - 1], nums[i]). Every pair collected so far had a larger gap, so it no longer qualifies. - Test for a tie with an
else ifoncurDiff == minDiff. - On a tie, append the same kind of pair.
- Return
minDiffPairsafter the loop.
The solution in Java
class Solution {
public List<List<Integer>> minimumAbsDifference(int[] nums) {
Arrays.sort(nums);
int minDiff = nums[1] - nums[0];
List<List<Integer>> minDiffPairs = new ArrayList<>();
for (int i = 1; i < nums.length; i++) {
int curDiff = nums[i] - nums[i - 1];
if (curDiff < minDiff) {
minDiff = curDiff;
minDiffPairs = new ArrayList<>();
minDiffPairs.add(Arrays.asList(nums[i - 1], nums[i]));
} else if (curDiff == minDiff) {
minDiffPairs.add(Arrays.asList(nums[i - 1], nums[i]));
}
}
return minDiffPairs;
}
}
The Java details worth a closer look:
- The first pair is added by the loop.
minDiffstarts as the first gap while the list starts empty. Ati = 1the gap equalsminDiff, so the tie branch adds the first pair. Arrays.sortchanges the caller's array. It sorts theint[]in place. Sort a copy if the original order must survive.Arrays.asList(nums[i - 1], nums[i])boxes the twointvalues intoIntegerobjects and returns a fixed-sizeList<Integer>, which fits inminDiffPairs. You can read it but not add to it or remove from it.- The subtraction can't overflow here. The values lie between -1,000,000 and 1,000,000, so a gap is at most 2,000,000. For arbitrary
intvalues,nums[i] - nums[i - 1]could exceed theintrange, and the arithmetic would needlong.
Complexity
Time: O(n log n). Sorting costs O(n log n) and the pass over neighbours costs O(n). This beats the O(n²) of checking every pair.
Space: O(1) beyond the output, apart from the sort's own working memory. The result list can hold up to n - 1 pairs, as in an evenly spaced array.
Edge cases and common mistakes
- Two elements.
[5, 2]sorts to[2, 5]and returns[[2, 5]]. - All gaps equal.
[1, 4, 7, 10]returns all three neighbour pairs. - Negative numbers.
[-5, -1, 3, 7]returns[[-5, -1], [-1, 3], [3, 7]]. Sorting handles negatives naturally. - Forgetting to reset the list. If a new record only appends, pairs with larger gaps stay in the result.
- Dropping the tie branch. The method would return one pair, not all of the tied ones.
- Forgetting to sort. Comparing neighbours in the original order finds nothing useful.
- A one-element array.
nums[1]would throw, but the statement guarantees at least two elements.
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]].[-5, -1, 3, 7]gives[[-5, -1], [-1, 3], [3, 7]].