Start learning free

LESSON 265 OF 414 · HASH TABLE

Two Sum in Rust: O(n) with a HashMap

Practice 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) time and use O(n) space.


Hints:

This the type of problem where we optimize the brute force approach to get the optimal one. The brute force approach took O(n^2) time because we had two nested for loops, one for i and another one j. In order to get O(n), we have to reduce this to only one for loop, so we should fix only one index, let it be j, the index of the second number. We will try out each possible j, and for each of them we should check if there is an index i < j such that nums[i] + nums[j] == target: 
for each j : 0 -> n - 1:
	// We know nums[j]. Find some index i < j such that nums[i] + nums[j] == target.
How can we find that index in O(1)?

nums[i] + nums[j] == target ⇔ nums[i] == target - nums[j]. So for each j, we should look for an element equal to target - nums[j] from the left of j. Is there a data structure that allows us to look for an element in a collection in constant time? How can we use it here?

That data structure is the Hash Map. We can have a Hash Map where we insert all the elements nums[j] we iterate on during the for loop. In this way, for each j, we can look in the Hash Map to see if there is some element of value target - nums[j] and if so, we found a solution: 
for each j : 0 -> n - 1:
	- Look for target - nums[j] in the Hash Map. If there exists, we found the solution.
	- Otherwise, insert nums[j] into the Hash Map and continue with the for loop.
I know the code above is not perfect. Hash Maps work with pairs (key => value), we cannot just insert a nums[j] into a Hash Map. What should we actually insert in this hash map? What are the keys and what are the values?

The problem with the code above is that we just check if there is an element equal to target - nums[j]. If so, we have a solution, but that's not enough. The problem asks us to return the indices of those elements and we only know of them: j. Can we adapt the solution such that if for some j there is an element equal to target - nums[j], we can also get its index?

The pairs in the Hash Map should be nums[j] => j so that for each element we insert, we can also get its index: 
for each j : 0 -> n - 1:
	if target - nums[j] in indexOfValue:
		return [indexOfValue[target - nums[j]], j]
	indexOfValue[nums[j]] = j
return [-1, -1]

STEP 1 OF 6
    Ctrl + Enter to check

    RUST · HASH TABLE

    Two Sum in Rust, explained

    Problem overview

    The function two_sum receives a vector of integers, nums, and a 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 valid pair, and the same index can't be used twice.

    For nums = [2, 7, 11, 15] and target = 9, the values 2 and 7 at indices 0 and 1 sum to 9. This solution returns the later index first, so the result is [1, 0]: the pair of indices is what matters, and this order is what the code produces.

    The lesson asks for O(n) time and O(n) extra space.

    Approach: remember what you have seen

    The brute force checks every pair of indices with two nested loops, which is O(n²). To reach O(n), keep a single loop and answer one question per element: has the partner of this element appeared earlier?

    If the current value is num, its partner must be target - num, the complement. Searching the earlier elements for it would be another loop, but a hash map answers "is this value present?" in O(1) on average. The map goes from a value to the index where it was seen: value as key, index as the stored value. Finding the complement then also gives you its index.

    Each loop iteration does two things in a fixed order: look up the complement, and only then insert the current element. Inserting afterwards means an element can never match itself, so index reuse is impossible. Two equal values still work, because the first is stored by the time the second arrives.

    On nums = [3, 2, 4] and target = 6: the map starts empty. Index 0 (value 3) needs 3, which is not there, so 3 is stored. Index 1 (value 2) needs 4, not there, so 2 is stored. Index 2 (value 4) needs 2, which is stored with index 1, so the function returns [2, 1]. The 3 at index 0 never pairs with itself.

    Step by step

    1. Import and create the map. HashMap is not in Rust's prelude, so add use std::collections::HashMap; above the impl. Then declare index_of_value as a mut map from i32 to i32.
    2. Loop with indices. nums.iter().enumerate() yields pairs of an index and a reference to the value. The pattern (i, &num) copies the number out of the reference.
    3. Look up the complement. Compute complement as target - num and ask the map for it. get takes a reference to the key and returns an Option of a reference. if let Some(&j) handles the found case and copies the stored index into j. On a hit, return both indices, converting i from usize with as i32.
    4. Record the current value after the check, with its index.
    5. Fall back to [-1, -1]. The loop only finishes without returning when no element found a partner.

    The solution in Rust

    use std::collections::HashMap;

impl Solution {
    fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut index_of_value: HashMap<i32, i32> = HashMap::new();
        for (i, &num) in nums.iter().enumerate() {
            let complement = target - num;
            if let Some(&j) = index_of_value.get(&complement) {
                return vec![i as i32, j];
            }
            index_of_value.insert(num, i as i32);
        }
        vec![-1, -1]
    }
}

    Rust details worth a closer look:

    • References in the loop. iter() yields &i32. Writing &num in the pattern dereferences it, so num is a plain i32.
    • Option patterns. get(&complement) returns Option<&i32>. In Some(&j), the & copies the integer out, so j is an i32 and the borrow of the map ends at once.
    • Casts. enumerate() counts in usize, while the function returns Vec<i32>, hence i as i32. The map stores i32 indices for the same reason. An as cast truncates silently if the value doesn't fit, which cannot happen for any realistic vector length here.
    • Ownership. nums is an owned Vec, but the loop only borrows it through iter(). Keys and values are i32, which is Copy, so inserting into the map moves nothing.
    • Return values. return vec![...] exits early from inside the loop. The last line, vec![-1, -1], has no semicolon, so it is the value of the function when the loop ends.

    Complexity

    Time: O(n). The loop runs at most n times, and each iteration does one lookup and one insertion, both O(1) on average.

    Space: O(n). In the worst case, when no pair exists, the map ends up holding every element.

    Edge cases and common mistakes

    • Empty vector or a single element. The loop finds no partner, and the function returns [-1, -1].
    • Equal values. [3, 3] with target 6 returns [1, 0]. The first 3 is stored before the second one looks for its complement.
    • Using an element twice. [3, 4] with target 6 returns [-1, -1]. If the insertion came before the lookup, the 3 would find itself.
    • Duplicate values with different roles. If a value appears twice, insert overwrites the earlier index. That can't lose an answer here: two equal values that sum to the target would already have been matched when the second one arrived.
    • Overflow. target - num is an i32 subtraction. With the optimized build, a result outside the i32 range wraps silently; in a debug build it panics. For target = -2_000_000_000 and num = 2_000_000_000, the wrapped complement is 294967296. If the inputs can approach the limits of i32, compute the complement in i64.
    • Negative numbers. They need no special handling: [-3, 4, 3, 90] with target 0 returns [2, 0].

    Testing

    • nums = [2, 7, 11, 15], target = 9 gives [1, 0].
    • nums = [3, 2, 4], target = 6 gives [2, 1].
    • nums = [3, 3], target = 6 gives [1, 0].
    • nums = [3, 4], target = 6 gives [-1, -1].
    • nums = [], target = 6 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