Solving the Two Sum Problem in Rust: Brute Force vs HashMap

I’ve been diving into Rust and decided to challenge myself with some LeetCode problems. One of the first ones I tackled was the classic Two Sum problem — and, it turned out to be a great way to practice Rust basics like iterating over vectors and using HashMap.

In this post, I’ll walk you through how I approached the problem first with a brute-force solution, and then optimized it using a hash map. I’ll also break down what “time complexity” really means as we go.

The Problem

You're given an array of integers nums and a target integer target. Your task is to:
Return the indices of the two numbers such that they add up to the target.

Constraints:

• Each input has exactly one solution.
• You can’t use the same element twice.
• You can return the answer in any order.

🧠 First Attempt: Brute Force

Here’s what I started with. Just loop through the list twice and try every possible pair of numbers:
src/lib.rs

pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    // Loop through each number with index i and value c
    for (i, c) in nums.iter().enumerate() {
        // Loop again for every possible pair
        for (j, c2) in nums.iter().enumerate() {
            // If indices are different and values add up to target, return them
            if i != j && c + c2 == target {
                return vec![i as i32, j as i32];
            }
        }
    }
    vec![] // Return empty vector if no pair is found 
}

⏱️ Time Complexity: O(n²)

This means if the list has:

• 10 numbers → ~100 comparisons,
• 1,000 numbers → ~1,000,000 comparisons.

Why? Because for each number in the list, I’m looping through the entire list again to check all combinations. That’s n times n, which is n².

Space Complexity: O(1)

I’m not storing any extra data structures, so the space stays constant, no matter how big the input is.

The Better Way: HashMap

The brute-force worked, but it wasn’t efficient — especially with larger inputs.
So I decided to use a HashMap to improve performance. Here’s the idea:

• While looping through the list, I check if the “complement” of the current number (i.e., target - current number) has already been seen.
• If it has, we’ve found our pair.
• Otherwise, I add the number and its index to the map.

src/lib.rs

use std::collections::HashMap;

pub fn two_sum_hashmap(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let mut map = HashMap::new(); // Create a HashMap to store number -> index

    for (i, c) in nums.iter().enumerate() {
        let complement = target - c; // Calculate the number we need to complete the target

        // Check if we already saw the complement before
        if let Some(&j) = map.get(&complement) {
            return vec![j, i as i32]; // If found, return the stored index and current index
        }

        // Otherwise, insert current number and index into the map
        map.insert(c, i as i32);
    }

    vec![] // Return empty vector if no solution found (shouldn't happen)
}

⏱️ Time Complexity: O(n)

Only one loop. For each number, we do a constant-time HashMap lookup. So the number of operations grows linearly with the input size.

• 10 numbers → 10 operations
• 1,000 numbers → 1,000 operations

Way faster than the brute-force approach.

Space Complexity: O(n)

We use a HashMap that stores up to n items — one for each number in the list.

✅ Tests to Make Sure It Works

I wrote some basic tests to make sure both versions work correctly:
src/lib.rs

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_two_sum() {
        let nums = vec![2, 7, 11, 15];
        let target = 9;
        let result = two_sum(nums, target);
        assert_eq!(result, vec![0, 1]); // 2 + 7 = 9
    }

    #[test]
    fn test_two_sum_hashmap() {
        let nums = vec![3, 2, 4];
        let target = 6;
        let result = two_sum_hashmap(nums, target);
        assert_eq!(result, vec![1, 2]); // 2 + 4 = 6
    }
}

Final Thoughts

Both versions solve the problem correctly — the brute-force is simple and clear, while the HashMapversion is more efficient and scalable.

• Nested loops are easy to write, but expensive in terms of performance.
• HashMaps are your best friend when you need fast lookups.
• Rust’s enumerate, iter, and HashMap are powerful once you get used to the syntax.

🔁 Use brute-force for learning, but aim for the HashMap solution in interviews or production code.

This exercise helped me practice both problem-solving and writing idiomatic Rust. If you’re also learning Rust and using LeetCode to improve, I’d love to hear how you’re approaching these problems!