Problem overview
The function minimum_abs_difference receives a vector of distinct integers, nums. It must find the smallest absolute difference between any two elements and return every pair [a, b] with a < b and b - a equal to that smallest difference. The pairs come back in ascending order.
For nums = [4, 2, 1, 3] the smallest difference is 1, and the pairs that achieve it are [1, 2], [2, 3] and [3, 4]. For [1, 3, 6, 10, 15] only [1, 3] has a gap of 2, so the answer is [[1, 3]]. The constraints allow up to 100,000 values between -1,000,000 and 1,000,000, and at least two of them.
Approach: after sorting, only neighbours matter
Comparing every pair of values would take O(n²) time, which is too slow for 100,000 elements. Sorting makes it unnecessary. In a sorted array, take any two values that are not neighbours. The value between them is closer to each of them than they are to each other, so a non-adjacent pair can never have the smallest gap. The closest pairs are always adjacent ones.
That gives a single pass over the sorted vector. Keep the smallest gap seen so far and the list of pairs that have it. Each adjacent pair has one of three outcomes:
- Its gap is smaller than the best: the old list is wrong, so start a new list with this pair.
- Its gap equals the best: add the pair to the list.
- Its gap is larger: ignore it.
Sorting also gives the output order for free. The pairs are produced from left to right, so both the pairs and the values inside each pair are already ascending. Take [3, 8, -10, 23, 19, -4, -14, 27]. Sorted, it is [-14, -10, -4, 3, 8, 19, 23, 27]. The gaps are 4, 6, 7, 5, 11, 4 and 4. The smallest, 4, is reached by [-14, -10], [19, 23] and [23, 27].
Step by step
- Sort in place.
sort()orders the vector ascending. It needs the parameter to be declaredmut nums. - Start with the first gap.
min_diffbegins asnums[1] - nums[0], a real gap, so no sentinel value is needed. The result listmin_diff_pairsbegins empty. - Loop over the adjacent pairs. The index
iruns from 1 to the last position, and each iteration looks at the pair ending ati. - Compute the current gap as
nums[i] - nums[i - 1]. It is never negative, because the vector is sorted. - Handle a smaller gap. Update
min_diffand replace the whole list with one pair, the current one. - Handle an equal gap in an
else if, and push the pair onto the list. - Return the list.
The first pair, nums[0] and nums[1], is covered by the loop's first iteration, which sees a gap equal to min_diff and pushes the pair. That is why the list can start empty.
The solution in Rust
impl Solution {
fn minimum_abs_difference(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
nums.sort();
let mut min_diff = nums[1] - nums[0];
let mut min_diff_pairs: Vec<Vec<i32>> = Vec::new();
for i in 1..nums.len() {
let cur_diff = nums[i] - nums[i - 1];
if cur_diff < min_diff {
min_diff = cur_diff;
min_diff_pairs = vec![vec![nums[i - 1], nums[i]]];
} else if cur_diff == min_diff {
min_diff_pairs.push(vec![nums[i - 1], nums[i]]);
}
}
return min_diff_pairs;
}
}
The Rust details worth a closer look:
Vec<Vec<i32>>. The result is a vector of vectors, each inner vector holding two numbers. Thevec![...]macro builds one, sovec![vec![a, b]]is a list that holds a single pair.- Replacing the list. Assigning a new vector to
min_diff_pairsdrops the old one and its contents. There is no need to callclear()first. - The type annotation.
Vec::new()alone doesn't say what the vector holds. The annotation onmin_diff_pairsgives the compiler the element type, although the laterpushcalls would also allow it to infer it. - Indexing panics.
nums[1]on a vector with fewer than two elements stops the program with an "index out of bounds" panic. The constraints guarantee two elements, so the lesson doesn't guard against it. 1..nums.len(). The range excludes its upper bound, soistops at the last valid index, andi - 1never goes below 0 becauseistarts at 1.- Integer overflow. The values stay within plus or minus 1,000,000, so a difference is at most 2,000,000 and fits easily in an
i32. With values near thei32limits the subtraction could wrap in an optimized build.
Complexity
Time: O(n log n). The sort costs O(n log n) and the loop makes one pass over the vector. Each step does constant work apart from pushing a pair onto the list.
Space: O(n) in the worst case for the output. If all gaps are equal, as in [1, 2, 3, 4], the result holds n - 1 pairs. Apart from the output, the function needs only min_diff, cur_diff and the loop index, since the sort works in place.
Edge cases and common mistakes
- Exactly two elements.
[9, 5]returns[[5, 9]]. The pair is reported in ascending order, not in input order. - Several pairs tied.
[4, 2, 1, 3]returns three pairs. Using<=in place of the separate equal-case branch would reset the list every time and keep only the last pair. - Forgetting to reset. If a smaller gap appears after a longer-gap pair was stored, the stored pairs must go. Pushing in both branches would leave stale pairs in the answer.
- Comparing the original order. Comparing neighbours of the unsorted vector finds nothing useful. Sort first.
- Negative values.
[-1000000, 1000000]returns[[-1000000, 1000000]]. The gap is 2,000,000, which fits in ani32.
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, 9]gives[[5, 9]].
