Two Sum Problem Classic Hash Solution in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Two Sum problem classic hash solution?

Use a hash map to store numbers and their indices while scanning the list once. For each number, check if the complement (target - current number) exists in the map to find the pair quickly.

intermediate

In the Two Sum hash solution, why do we check for the complement before inserting the current number into the hash map?

Checking for the complement first ensures we don't use the same element twice and find the correct pair as soon as possible during the single pass.

beginner

What is the time complexity of the Two Sum problem classic hash solution?

The time complexity is O(n), where n is the number of elements, because each element is processed once and hash map lookups are O(1) on average.

beginner

Rust code snippet: What does this line do?
`let complement = target - num;`

It calculates the number needed to reach the target sum when added to the current number `num`. This complement is then searched in the hash map.

beginner

Why is a hash map preferred over nested loops for the Two Sum problem?

A hash map reduces the time complexity from O(n²) with nested loops to O(n) by enabling quick lookups of complements instead of checking all pairs.

What data structure is used in the classic Two Sum hash solution to store numbers and indices?

A Hash map

B Array

C Linked list

D Stack

The hash map stores numbers as keys and their indices as values for quick complement lookup.

What is the time complexity of the classic Two Sum hash solution?

A O(n²)

B O(n log n)

C O(n)

D O(log n)

The solution scans the list once and uses O(1) average time hash lookups, resulting in O(n) time complexity.

In the Two Sum hash solution, what do you do if the complement is not found in the hash map?

A Return immediately

B Sort the array

C Skip the current number

D Insert the current number and its index into the hash map

If complement is not found, insert the current number and index to check for future complements.

Why do we only need one pass through the array in the hash solution?

A Because the array is sorted

B Because hash map lookups are fast and we check complements on the fly

C Because we only need the first element

D Because the target is zero

One pass is enough since we check for complements in the hash map as we go.

What does the complement represent in the Two Sum problem?

A The difference between target and current number

B The current number itself

C The sum of all numbers

D The index of the current number

Complement is target minus the current number, the needed partner to reach the target sum.

Explain how the classic hash map solution for the Two Sum problem works step-by-step.

Think about how you find pairs quickly without checking all pairs.

Why is the hash map approach more efficient than the brute force nested loops for Two Sum?

Focus on how many times you check pairs in each approach.

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