LESSON 256 OF 414 · TWO POINTERS

Two Sum in Rust: O(n log n) with Sorting and Two Pointers

Practice O(n log n) + O(n) Read the full explanation

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input will have at most one solution, and you may not use the same index twice.

In case no solution exists, return [-1, -1]

Example:

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9

Note:

Your algorithm should run in O(n log n) time and use O(n) extra space.

STEP 1 OF 9

Guided

Ctrl + Enter to check

RUST · TWO POINTERS

Two Sum in Rust, explained

Problem overview

The function two_sum takes a vector nums and an integer target. It returns the indices of two different positions whose values add up to target, or [-1, -1] when there is no such pair. There is at most one solution, and one index can't be used twice, although two equal values at different indices are fine.

For nums = [2, 7, 11, 15] and target = 9, the values at indices 0 and 1 give 2 + 7 = 9, so the answer is [0, 1]. The statement asks for O(n log n) time and O(n) extra space.

Approach: sort, then squeeze from both ends

Checking every pair of indices costs O(n²). A sorted vector allows something much cheaper. Put one pointer, first, on the smallest value and another, last, on the largest, and look at their sum:

If the sum equals target, the pair is found.
If the sum is too small, the value at first can't be part of any answer with anything still in range, because even the largest remaining partner is not enough. Move first right.
If the sum is too large, the value at last is too big even with the smallest remaining partner. Move last left.

Each move rules out one element for good, so the pointers meet after at most n - 1 steps. The sorting dominates and costs O(n log n).

Sorting has a catch: it moves values away from their original positions, and the answer needs the original indices. The fix is to sort (value, original_index) pairs. Each value carries its index wherever the sort puts it.

Take nums = [3, 9, -2, 5] with target = 3. The sorted pairs are [(-2, 2), (3, 0), (5, 3), (9, 1)]. The sum of the two ends is -2 + 9 = 7, which is too large, so last moves left. Then -2 + 5 = 3 matches, and the answer is the original indices [2, 3].

Step by step

Pair values with indices. Declare sorted_nums as a mutable Vec<(i32, i32)>. Start from nums.iter(), attach positions with enumerate(), turn each (i, &v) into (v, i as i32) with map, and collect(). The value comes first in the tuple so that it drives the ordering.
Sort with sort(). Tuples compare field by field, so the pairs end up in ascending order of value, with ties broken by index.
Place the pointers. first is 0usize and last is sorted_nums.len() - 1, the two ends of the sorted vector.
Loop while first < last. When they meet, every pair has been ruled out.
Add the two values, sorted_nums[first].0 and sorted_nums[last].0, into sum. In each tuple, .0 is the value and .1 is the original index.
Match. When sum == target, return a vec! of the two original indices, sorted_nums[first].1 and sorted_nums[last].1. The return keyword is needed because the function ends from inside the loop.
Too small. In an else if sum < target branch, do first += 1.
Too large. In the final else branch, do last -= 1.
No pair. After the loop, the final expression vec![-1, -1] is the answer.

The solution in Rust

impl Solution {
    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();

        let mut first = 0usize;
        let mut last = sorted_nums.len() - 1;
        while first < last {
            let sum = sorted_nums[first].0 + sorted_nums[last].0;
            if sum == target {
                return vec![sorted_nums[first].1, sorted_nums[last].1];
            } else if sum < target {
                first += 1;
            } else {
                last -= 1;
            }
        }
        vec![-1, -1]
    }
}

Rust details worth knowing:

The iterator chain. nums.iter() yields &i32 references. enumerate() wraps each in a (usize, &i32) tuple. The closure pattern |(i, &v)| takes the tuple apart and copies the number out of the reference. The annotation on sorted_nums tells collect() to build a Vec<(i32, i32)>.
The cast. i as i32 converts the usize position to the tuple's i32. Casts with as never fail; they truncate silently when a value doesn't fit. That is harmless for any realistic vector length.
Ordering the result. The first returned index belongs to the smaller value. For [7, 2] and target 9 the answer is [1, 0].
Equal values. Two equal numbers sort next to each other, so [3, 3] with target 6 returns [0, 1]: they are different positions, and the pointers sit on different elements.
Tail expression. vec![-1, -1] has no semicolon and is the value returned when no return fires.

Complexity

Time: O(n log n). Building the pairs is O(n), sorting is O(n log n), and the two-pointer sweep is O(n), since each iteration moves one pointer and they travel at most n positions in total.

Space: O(n). The vector of pairs holds one tuple per element. The sweep uses a few integers.

Edge cases and common mistakes

Empty input. sorted_nums.len() - 1 is 0 minus 1 for an empty vector. In an optimized build this wraps to the largest usize, the loop starts, and indexing position 0 panics with "index out of bounds: the len is 0". In a debug build the subtraction itself panics. The lesson's inputs have elements, but a guard such as returning vec![-1, -1] when nums.len() < 2 makes the function safe.
One element. first and last are both 0, so the loop doesn't run and the answer is [-1, -1]. An element can't pair with itself.
Overflow in the sum. The addition is done in i32. In an optimized build, [2000000000, 2000000000] with target -294967296 wraps the sum to exactly -294967296 and returns [0, 1], which is wrong. In a debug build the addition would panic. Adding as i64 avoids both.
Returning sorted positions. first and last are positions in the sorted vector. The answer comes from the .1 fields.
Sorting without indices. A plain sorted Vec<i32> finds the right values but loses where they were.
Using first <= last. That would let an element pair with itself: [3, 4] with target 6 would return [0, 0].

Testing

nums = [2, 7, 11, 15], target = 9 gives [0, 1].
nums = [3, 9, -2, 5], target = 3 gives [2, 3].
nums = [3, 3], target = 6 gives [0, 1].
nums = [3, 4], target = 6 gives [-1, -1].
nums = [1, 2, 3], target = 100 gives [-1, -1].

Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free