Problem overview
The function two_sum receives a vector of integers, nums, and a target. It must return the indices of two different positions whose values add up to target, or [-1, -1] when no such pair exists. There is at most one valid pair, and the same index can't be used twice, although two equal values at different indices are fine.
In the example, nums = [2, 7, 11, 15] and target = 9. The values at indices 0 and 1 are 2 and 7, which sum to 9, so the answer is [0, 1].
The statement also sets a budget: O(n log n) time and O(n) extra space. That rules out checking every pair and points toward sorting.
Approach: sort the pairs, then search for each complement
The brute-force idea tries every pair of indices, which is O(n²). The faster idea rests on one observation: if a value x is part of the answer, its partner must be exactly target - x, the complement. Looking up a specific value in a sorted array takes O(log n) with binary search, so one search per element gives O(n log n) overall.
Sorting creates a problem, though: it moves values away from their original positions, and the answer has to use the original indices. The fix is to sort (value, original_index) pairs instead of bare values. Each value carries its index with it, wherever the sort puts it.
The search for the partner of position i only looks at positions i + 1 and beyond. Every pair of positions has a left member, and the pair is found when the loop reaches it, so looking left would only repeat earlier work. Starting at i + 1 also stops an element from being paired with itself.
Here is the idea on nums = [3, 9, -2, 5] with target = 3. The sorted pairs are [(-2, 2), (3, 0), (5, 3), (9, 1)]. At position 0 the value is -2, so the search looks for 5 among positions 1 to 3. The midpoint, position 2, holds 5, so the function returns the original indices of positions 0 and 2: [2, 3].
Two Sum can be solved in other ways too. A hash map of the values seen so far reaches O(n) time, and a two-pointer scan over the same sorted pairs runs in O(n log n) because of the sort. This lesson practises binary search, so it searches for each complement directly.
Step by step
- Pair each value with its index. The value goes first in the tuple so that sorting orders the pairs by value.
- Sort the pairs. After this, the values are in ascending order, which is what binary search needs.
- Record the length as
n, ausize, for the loop and the search bounds. - Loop over the positions and stop as soon as there is no position to the right of
i. The last element has no partner left to search, so the loop ends there instead of searching an empty range. - Compute the complement in
i64and skip this position if it falls outside thei32range. No element can hold such a value, so there is nothing to search for. - Search positions
i + 1ton - 1with the helper, which returns a position in the sorted pairs or -1. - On a hit, return the original indices stored in the second field of both pairs, not the sorted positions.
- Fall back to
[-1, -1]when the loop finishes without a match. - Write the helper's signature. It borrows the pairs as a slice and takes the inclusive range to search and the value to find.
- Convert both bounds to
i64. The upper bound can drop below the lower one, and in general below zero, which ausizecan't represent. - Loop while the range is non-empty, that is, while
lo <= hi. - Take the midpoint as
lo + (hi - lo) / 2and convert it tousizefor indexing. - Compare and halve the range. Return the midpoint on a match; otherwise discard the half that can't contain the value.
- Return -1 once the range is empty.
The solution in Rust
impl Solution {
fn binary_search_idx(sorted_nums: &[(i32, i32)], first: usize, last: usize, value: i32) -> i32 {
let mut lo = first as i64;
let mut hi = last as i64;
while lo <= hi {
let mid = lo + (hi - lo) / 2;
let mid_u = mid as usize;
if sorted_nums[mid_u].0 == value {
return mid as i32;
} else if sorted_nums[mid_u].0 < value {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
-1
}
fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut sorted_nums: Vec<(i32, i32)> = nums
.iter()
.enumerate()
.map(|(i, &v)| (v, i as i32))
.collect();
sorted_nums.sort_unstable();
let n = sorted_nums.len();
for i in 0..n {
if i + 1 >= n {
break;
}
let need = (target as i64) - (sorted_nums[i].0 as i64);
if need < i32::MIN as i64 || need > i32::MAX as i64 {
continue;
}
let j = Self::binary_search_idx(&sorted_nums, i + 1, n - 1, need as i32);
if j != -1 {
return vec![sorted_nums[i].1, sorted_nums[j as usize].1];
}
}
vec![-1, -1]
}
}
The Rust details worth a closer look:
- The iterator chain.
nums.iter()yields&i32references andenumerate()wraps each in a(usize, &i32)tuple. The closure pattern|(i, &v)|destructures that tuple and copies the value out of the reference. The type annotation onsorted_numstellscollect()to build aVec<(i32, i32)>. - Sorting tuples. Tuples compare field by field, so the value decides the order and the index breaks ties. Since every index is unique, no two pairs are equal, and an unstable sort produces the same result a stable one would.
sort_unstablealso sorts in place without allocating. asnever panics. Casting between integer types silently truncates:3_000_000_000_i64 as i32is-1294967296. That is why the range check comes beforeneed as i32.usizeunderflow does panic. In a debug build, subtracting 1 from ausizethat holds 0 stops the program with an overflow panic. The helper therefore works withi64bounds, andtwo_sumuses thebreakguard instead of a loop over0..n - 1, which would underflow for an empty input.- Slices and associated functions. The helper takes no
self, so it is called asSelf::binary_search_idx. Passing&sorted_nums, a&Vec<(i32, i32)>, works because Rust coerces it to the slice type&[(i32, i32)]. - Final expressions.
-1andvec![-1, -1]have no semicolon, so they are the values the functions return when no earlierreturnfires.
Complexity
Time: O(n log n). Building the pairs is O(n) and sorting them is O(n log n). The loop runs at most n - 1 binary searches, each halving its range until it is empty, so each costs O(log n). The sort and the searches both stay within O(n log n).
Space: O(n). The vector of pairs holds one tuple per element. The sort works in place, and the helper uses a few integers.
Edge cases and common mistakes
- Fewer than two elements. For an empty vector the loop never runs, and for a single element it breaks immediately. Both return
[-1, -1]without panicking. - Equal values.
[3, 3]with target 6 returns[0, 1]: the two 3s are different pairs, and the search for the second one starts at position 1. - Pairing an element with itself.
[3, 4]with target 6 must return[-1, -1]. Searching from position 0 instead ofi + 1would find the same 3 and answer[0, 0]. - Overflow. With
target = -2_000_000_000and an element equal to2_000_000_000, subtracting ini32overflows, which panics in a debug build. Ini64the complement, -4,000,000,000, is computed exactly and skipped. - Returning sorted positions.
iandjare positions in the sorted vector. The answer comes from the.1fields. - Using
lo < hi. When the search range is a single element,loequalshi. With a strict comparison that element is never checked, so[2, 7]with target 9 would wrongly return[-1, -1]. - Index order. The index of the smaller value always comes first. For
[7, 2]and target 9 the function returns[1, 0].
Testing
nums = [2, 7, 11, 15],target = 9gives[0, 1].nums = [3, 9, -2, 5],target = 3gives[2, 3].nums = [-3, 4, 3, 90],target = 0gives[0, 2].nums = [1, 2, 3],target = 100gives[-1, -1].nums = [],target = 5gives[-1, -1].
