Solving LeetCode Two Sum in Rust – A Practical Walkthrough

Welcome to the very first post on Karan @ Lumetium! Today, we’re kicking things off with a classic algorithmic challenge: the Two Sum problem from LeetCode. We’ll walk through the problem statement, discuss a performant approach, and implement our solution in Rust—step by step.

1. Problem Statement

LeetCode #1: Two Sum
Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.

Example

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

2. Thinking Through the Approach

There are multiple ways to solve this:

• Brute-Force (O(n²)): Check every pair — easy but slow for large inputs.
• Two-Pass Hash Map (O(n)): First build a map from value → index, then for each element check if target - nums[i]exists.
• One-Pass Hash Map (O(n)): Build the map on the fly as you iterate, checking for complements immediately.

I prefer the one-pass method because it’s both fast and memory-efficient. As we scan the list, we look up each complement in our hash map; if found, we’ve got our answer. If not, we insert the current value.

3. Implementation in Rust

use std::collections::HashMap;

pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<usize> {
    let mut map: HashMap<i32, usize> = HashMap::with_capacity(nums.len());
    
    for (i, &num) in nums.iter().enumerate() {
        let complement = target - num;
        if let Some(&j) = map.get(&complement) {
            return vec![j, i];
        }
        map.insert(num, i);
    }
    
    // By problem constraints, this line is never reached.
    unreachable!("No two sum solution found");
}

fn main() {
    let nums = vec![2, 7, 11, 15];
    let result = two_sum(nums, 9);
    println!("Indices: {:?}", result); // Output: Indices: [0, 1]
}

Key Points

• HashMap Capacity: We preallocate with nums.len() to avoid unnecessary resizes.
• Enumerate: Gives us both the index i and the value num.
• if let Some syntax keeps our lookup and unwrap concise.
• unreachable!() signals to both the compiler and fellow readers that—per problem guarantees—this line should never execute.

4. Time & Space Complexity

• Time: O(n), where n = number of elements in nums. We make a single pass, doing O(1) hash-map operations each.
• Space: O(n) for storing up to n entries in the map.

5. What’s Next?

• I’ll be posting weekly LeetCode walkthroughs—from classic patterns to advanced topics.
• Up next: a deep dive into dynamic programming with the “Climbing Stairs” problem.
• Plus, I’ll sprinkle in infrastructure tutorials (think Terraform + AWS) and end-to-end CRUD builds.

Stay tuned, and don’t hesitate to drop questions or alternative optimizations in the comments below. Let’s learn together!

Code. Configure. Conquer.
— Karan at Lumetium