Two Sum Problem Classic Hash Solution in DSA Rust - Execution Trace

Concept Flow - Two Sum Problem Classic Hash Solution

Start with empty hash map

↓

Iterate over array elements

↓

Calculate complement = target - current element

↓

Check if complement in hash map?

Yes→Return indices

No↓

Add current element and index to hash map

↓

Repeat until found or end

↓

If no pair found, return None

We scan the array once, storing elements in a hash map. For each element, we check if its complement exists in the map to find the pair quickly.

Execution Sample

DSA Rust

fn two_sum(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    let mut map = std::collections::HashMap::new();
    for (i, &num) in nums.iter().enumerate() {
        let complement = target - num;
        if let Some(&j) = map.get(&complement) {
            return Some((j, i));
        }
        map.insert(num, i);
    }
    None
}

This code finds two indices in nums whose values add up to target using a hash map for fast lookup.

Execution Table

Step	Operation	Current Element (num)	Complement (target - num)	Hash Map State	Action	Result
1	Start iteration	-	-	{}	Initialize empty map	-
2	Check complement	2	7	{}	7 not in map	Insert (2:0)
3	Check complement	7	2	{2:0}	2 found in map	Return indices (0,1)
Exit	Found pair	-	-	-	-	Stop and return (0,1)

💡 At step 3, complement 2 is found in the map, so indices (0,1) are returned.

Variable Tracker

Variable	Start	After Step 2	After Step 3	Final
map	{}	{2:0}	{2:0}	{2:0}
i	-	0	1	1
num	-	2	7	7
complement	-	7	2	2

Key Moments - 3 Insights

Why do we check if the complement is in the map before inserting the current element?

Because we want to find if a previously seen number pairs with the current one. Checking first (see step 3 in execution_table) ensures we don't miss the pair or use the same element twice.

What happens if the pair is not found in the entire array?

The loop finishes without returning (see exit_note). Then the function returns None, meaning no two numbers add up to the target.

Why do we store the number as key and index as value in the map?

We store number → index so when we find a complement, we can quickly get the index of the first number to return the pair of indices.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the hash map state after inserting the first element?

A {"7":0}

B {}

C {"2":0}

D {"2":1}

💡 Hint

Check the 'Hash Map State' and 'Action' columns at step 2 in the execution_table.

At which step does the function find the complement in the map and return the result?

A Step 1

B Step 3

C Step 2

D Exit step

💡 Hint

Look for the step where 'complement found in map' and 'Return indices' appear in the execution_table.

If the target was 10 instead of 9, what would happen at step 3 in the execution_table?

A Complement would not be found, insert current element

B Complement would be found and return indices

C Function would return None immediately

D Hash map would be empty

💡 Hint

Think about how complement calculation changes and check the 'Action' column logic in the execution_table.

Concept Snapshot

Two Sum Classic Hash Solution:
- Use a hash map to store number → index
- For each number, compute complement = target - number
- Check if complement exists in map
- If yes, return indices
- Else, insert current number and index
- Runs in O(n) time with O(n) space

Full Transcript

The Two Sum problem finds two numbers in an array that add up to a target. This classic hash solution uses a hash map to store numbers and their indices as we scan the array. For each number, we calculate its complement (target minus the number) and check if this complement is already in the map. If found, we return the pair of indices immediately. Otherwise, we add the current number and its index to the map and continue. This approach ensures we find the pair in one pass efficiently. If no pair exists, the function returns None.

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