Two Sum Problem Classic Hash Solution in DSA Rust

Mental Model

We want to find two numbers that add up to a target by remembering numbers we've seen before.

Analogy: Imagine shopping with a list and a basket. You check each item and remember what you need to reach your total. If the needed item is already in your basket, you found the pair.

nums: [2] [7] [11] [15]
indices:  0   1    2    3
hash_map: {}
↑ current index at 0

Dry Run Walkthrough

Input: nums: [2, 7, 11, 15], target: 9

Goal: Find indices of two numbers that add up to 9

Step 1: Check number 2 at index 0, look for 9 - 2 = 7 in hash_map

hash_map: {}
nums: [2] [7] [11] [15]
indices:  0   1    2    3
↑ at index 0

Why: We want to see if the needed pair number 7 is already seen

Step 2: 7 not found in hash_map, add 2 with index 0 to hash_map

hash_map: {2:0}
nums: [2] [7] [11] [15]
indices:  0   1    2    3
↑ at index 1

Why: Remember 2's index for future pairs

Step 3: Check number 7 at index 1, look for 9 - 7 = 2 in hash_map

hash_map: {2:0}
nums: [2] [7] [11] [15]
indices:  0   1    2    3
↑ at index 1

Why: Check if 2 is already seen to form the pair

Step 4: 2 found in hash_map at index 0, return indices [0, 1]

hash_map: {2:0}
nums: [2] [7] [11] [15]
indices:  0   1    2    3
Pair found: indices 0 and 1

Why: We found two numbers that add up to target

Result:

Indices: [0, 1]

Annotated Code

DSA Rust

use std::collections::HashMap;

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

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

for (i, &num) in nums.iter().enumerate() {

iterate over each number with its index

let complement = target - num;

calculate the needed number to reach target

if let Some(&index) = map.get(&complement) {

check if complement is already seen

return vec![index as i32, i as i32];

return indices of the pair found

map.insert(num, i);

store current number and its index for future checks

Output

Indices: [0, 1]

Complexity Analysis

Time: O(n) because we scan the list once and do constant time lookups in the hash map

Space: O(n) because in the worst case we store all numbers in the hash map

vs Alternative: Compared to checking all pairs (O(n^2)), this hash map method is much faster by remembering seen numbers

Edge Cases

empty list

returns empty vector since no pairs exist

DSA Rust

vec![]

no two numbers sum to target

returns empty vector as no pair found

DSA Rust

vec![]

multiple pairs possible

returns the first valid pair found

DSA Rust

return vec![index as i32, i as i32];

When to Use This Pattern

When you need to find two elements that sum to a target quickly, use a hash map to remember seen numbers for O(n) lookup.

Common Mistakes

Mistake: Checking pairs with nested loops causing O(n^2) time
Fix: Use a hash map to store seen numbers and check complements in O(1)

Mistake: Inserting current number before checking complement causing wrong results
Fix: Check complement first, then insert current number

Summary

Find two indices whose numbers add up to the target using a hash map.

Use when you want a fast solution to find pairs summing to a target.

Remember the needed complement and check if it was seen before to find pairs in one pass.

Practice

1. What is the main purpose of using a hash map in the Two Sum problem classic hash solution?

easy

A. To reverse the array elements

B. To sort the array before searching

C. To store the sum of all pairs

D. To store numbers and their indices for quick lookup

Solution

1. Step 1: Understand the role of hash map

   The hash map stores each number as a key and its index as the value for quick access.

2. Step 2: Use hash map for complement lookup

   For each number, we check if the complement (target - number) exists in the hash map to find the pair.

3. Final Answer:

   To store numbers and their indices for quick lookup -> Option D

4. Quick Check:

   Hash map stores number:index pairs [OK]

Hint: Hash map helps find complements fast by storing indices [OK]

Common Mistakes:

• Thinking hash map sorts the array
• Trying to store sums instead of indices
• Using hash map to reverse elements

2. Which of the following Rust code snippets correctly declares a mutable hash map to solve the Two Sum problem?

easy

A. let map = HashMap::new();

B. let mut map = std::collections::HashMap::new();

C. let mut map = HashMap::new();

D. let map = std::collections::HashMap::new();

Solution

1. Step 1: Identify mutable hash map declaration

   To insert elements, the hash map must be mutable, so use 'let mut'.

2. Step 2: Use full path or import HashMap

   Using 'std::collections::HashMap::new()' is correct if HashMap is not imported.

3. Final Answer:

   let mut map = std::collections::HashMap::new(); -> Option B

4. Quick Check:

   Mutable hash map declaration requires 'mut' [OK]

Hint: Use 'let mut' to allow inserting into hash map [OK]

Common Mistakes:

• Forgetting 'mut' keyword for mutable map
• Using HashMap without importing or full path
• Declaring map immutable when insertions needed

3. What will be the output of the following Rust code snippet for the Two Sum problem?

fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let mut map = std::collections::HashMap::new();
    for (i, &num) in nums.iter().enumerate() {
        if let Some(&index) = map.get(&(target - num)) {
            return vec![index as i32, i as i32];
        }
        map.insert(num, i);
    }
    vec![]
}

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

medium

A. [2, 3]

B. [1, 0]

C. [0, 1]

D. []

Solution

1. Step 1: Iterate and check complements

   At i=0, num=2, map empty, insert (2,0). At i=1, num=7, complement=9-7=2 found at index 0.

2. Step 2: Return indices of complement pair

   Return vector with indices [0,1] as the pair sums to target 9.

3. Final Answer:

   [0, 1] -> Option C

4. Quick Check:

   Indices of 2 and 7 are [0,1] [OK]

Hint: Check complement in map before inserting current number [OK]

Common Mistakes:

• Returning indices in wrong order
• Not casting usize to i32 for return
• Returning empty vector when pair exists

4. Identify the bug in this Rust Two Sum solution and select the fix:

fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let mut map = std::collections::HashMap::new();
    for (i, num) in nums.iter().enumerate() {
        if let Some(&index) = map.get(&(target - num)) {
            return vec![index as i32, i as i32];
        }
        map.insert(num, i);
    }
    vec![]
}

medium

A. Change 'num' to '*num' in map.insert to match key type

B. Remove 'as i32' casts from return vector

C. Change 'map.get(&(target - num))' to 'map.get(&(target + num))'

D. Declare map as immutable instead of mutable

Solution

1. Step 1: Check key types in hash map

   Keys are i32 values, but 'num' is a reference (&i32), so insert needs dereferenced value.

2. Step 2: Fix insertion to use dereferenced num

   Change 'map.insert(num, i);' to 'map.insert(*num, i);' to insert i32 key, matching get() key type.

3. Final Answer:

   Change 'num' to '*num' in map.insert to match key type -> Option A

4. Quick Check:

   Dereference num when inserting key [OK]

Hint: Dereference iterator item before inserting into hash map [OK]

Common Mistakes:

• Inserting reference instead of value as key
• Changing target arithmetic incorrectly
• Making map immutable causing insert error

5. Given the input array [3, 3, 4, 5] and target 6, what will the Two Sum classic hash solution return and why?

hard

A. [0, 1] because the first two 3's sum to 6

B. [1, 2] because 3 and 4 sum to 7, closest to 6

C. [2, 3] because 4 and 5 sum to 9, which is greater than 6

D. [] because no two numbers sum exactly to 6

Solution

1. Step 1: Check pairs for target sum

   The first element 3 at index 0 is inserted. At index 1, num=3, complement=6-3=3 found at index 0.

2. Step 2: Return indices of first matching pair

   Return [0,1] because these two 3's sum exactly to 6.

3. Final Answer:

   [0, 1] because the first two 3's sum to 6 -> Option A

4. Quick Check:

   First pair summing to target returned [OK]

Hint: Return first found pair that sums to target [OK]

Common Mistakes:

• Choosing pairs that don't sum to target
• Ignoring duplicate values as valid pairs
• Returning empty vector incorrectly