Problem overview
The function minimum_abs_difference receives a vector of distinct integers, nums, with at least two elements. Among all pairs of elements, find the smallest absolute difference, then return every pair that reaches it. 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 difference is 1, reached by 1 and 2, by 2 and 3, and by 3 and 4. The answer is [[1, 2], [2, 3], [3, 4]]. For [1, 3, 6, 10, 15] only 1 and 3 are 2 apart, and nothing is closer, so the answer is [[1, 3]].
Approach: look at every pair and keep the best
With n numbers there are n(n - 1) / 2 pairs, so the brute-force method simply visits them all. For each pair it computes the absolute difference and compares it with the best difference seen so far:
- A smaller difference is a new record. Every pair collected earlier is now worse, so the list is replaced by a list holding only this pair.
- An equal difference ties the record, so this pair is added to the list.
- A larger difference is ignored.
The loops need the best difference to start somewhere. The lesson starts it as the difference of the first two elements, which is a real value from the input, so no artificial "infinity" is needed. Since that first pair is visited again by the loops and ties with itself, it ends up in the list through the tie branch.
Each pair is stored with the smaller value first, using min and max, because the loops may meet the two values in either order. Finally the list is sorted by the first element of each pair. All values are distinct, so two pairs with the same difference can't share their first element, and sorting by it alone gives a single correct order.
Step by step
- Set the starting record. Declare
min_diffas a mutable variable holding(nums[0] - nums[1]).abs(). Declaremin_diff_pairsas a mutableVec<Vec<i32>>created withVec::new(). - Loop over the first element of each pair with
iin0..nums.len(). - Loop over the second element with
jin(i + 1)..nums.len(). Starting ati + 1visits each pair once and never pairs an element with itself. - Compute
cur_diff, the absolute difference ofnums[i]andnums[j]. - Test for a new record with
cur_diff < min_diff. - On a record, store the new difference and replace the pair list with a vector holding just this pair, smaller value first.
- Test for a tie with an
else ifoncur_diff == min_diff. - On a tie, push the pair onto
min_diff_pairs. - After both loops, sort the pairs in place with
sort_by_key, using the first element of each pair as the key. - Return
min_diff_pairsas the last expression.
The solution in Rust
impl Solution {
fn minimum_abs_difference(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut min_diff = (nums[0] - nums[1]).abs();
let mut min_diff_pairs: Vec<Vec<i32>> = Vec::new();
for i in 0..nums.len() {
for j in (i + 1)..nums.len() {
let cur_diff = (nums[i] - nums[j]).abs();
if cur_diff < min_diff {
min_diff = cur_diff;
min_diff_pairs = vec![vec![nums[i].min(nums[j]), nums[i].max(nums[j])]];
} else if cur_diff == min_diff {
min_diff_pairs.push(vec![nums[i].min(nums[j]), nums[i].max(nums[j])]);
}
}
}
min_diff_pairs.sort_by_key(|pair| pair[0]);
min_diff_pairs
}
}
The Rust details worth a closer look:
- Method call order. In
(nums[i] - nums[j]).abs()the parentheses matter. Without them,.abs()would apply tonums[j]alone, before the subtraction. minandmaxare methods.nums[i].min(nums[j])returns the smaller of twoi32values, andmaxthe larger. They put each pair in[smaller, larger]order whichever way round the loops met it.- Vectors of vectors.
vec![nums[i].min(nums[j]), nums[i].max(nums[j])]builds a two-elementVec<i32>. Wrapping it in anothervec![...]builds aVec<Vec<i32>>with one pair, which replaces the old list on a new record. - Reassigning a
mutvariable. The assignment tomin_diff_pairsdrops the old list and moves the new one in. That is why the variable is declaredmut. sort_by_keywith a closure. The closure|pair| pair[0]receives a reference to each pair and returns the key to compare. Becausei32is copied out, the key doesn't borrow the pair.- Difference range. The values lie between -1,000,000 and 1,000,000, so a difference is at most 2,000,000 and fits comfortably in an
i32. For inputs near thei32limits, a subtraction could overflow, wrapping silently in an optimized build and panicking in a debug build.
Complexity
Time: O(n^2) plus the sort. The two loops visit n(n - 1) / 2 pairs and do constant work for each, apart from occasionally allocating a small vector. The final sort costs O(k log k) for k stored pairs, and k is below n, so the loops dominate.
Space: O(k) for the answer. Besides the returned list, the function keeps only a few integers. Faster solutions for this problem exist, since sorting the numbers first leaves only neighbouring values to compare.
Edge cases and common mistakes
- Exactly two elements. For
[9, 1]the only pair is stored as[1, 9], with the smaller value first. - Fewer than two elements. The first line indexes
nums[1], which panics for an empty or one-element vector. The problem guarantees at least two elements. - Not clearing the list on a new record. Pairs from an older, larger difference would stay in the answer.
- Writing
<=instead of the separate tie branch. A tie must add a pair, not replace the list. - Forgetting the final sort. The loops find pairs in the order of the input, so
[4, 2, 1, 3]would produce the pairs in the order [3, 4], [1, 2], [2, 3] without the sort. - Negative numbers. For
[3, 8, -10, 23, 19, -4, -14, 27]the answer is[[-14, -10], [19, 23], [23, 27]]. The absolute value makes the sign irrelevant, and the sort handles negative keys.
Testing
nums = [4, 2, 1, 3]gives[[1, 2], [2, 3], [3, 4]].nums = [1, 3, 6, 10, 15]gives[[1, 3]].nums = [3, 8, -10, 23, 19, -4, -14, 27]gives[[-14, -10], [19, 23], [23, 27]].nums = [9, 1]gives[[1, 9]].
