Two Sum Problem Classic Hash Solution in DSA C++ - Execution Trace

Concept Flow - Two Sum Problem Classic Hash Solution

Start with empty hash map

↓

For each number in array

↓

Calculate complement = target - current number

↓

Check if complement in hash map?

Yes→Return indices

No↓

Add current number and index to hash map

↓

Repeat for next number

↓

If no pair found

→Return no solution

We scan the array once, storing numbers and their indices in a hash map. For each number, we check if the complement to reach the target exists in the map. If yes, we return the pair.

Execution Sample

DSA C++

vector<int> twoSum(vector<int>& nums, int target) {
  unordered_map<int,int> map;
  for (int i = 0; i < nums.size(); i++) {
    int comp = target - nums[i];
    if (map.count(comp)) return {map[comp], i};
    map[nums[i]] = i;
  }
  return {};
}

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 Number (nums[i])	Complement (target - nums[i])	Hash Map State (number:index)	Action	Result/Output
1	Start loop	-	-	{}	Check complement in map	No complement found
2	Process nums[0]	2	7	{}	Add 2:0 to map	Map updated
3	Process nums[1]	7	2	{2:0}	Complement 2 found in map	Return indices [0,1]
4	End	-	-	-	-	Solution found, loop ends

💡 At step 3, complement 2 is found in map, so indices [0,1] are returned and execution stops.

Variable Tracker

Variable	Start	After Step 2	After Step 3	Final
i	-	0	1	1
nums[i]	-	2	7	7
complement	-	7	2	2
hash_map	{}	{2:0}	{2:0}	{2:0}
result	-	-	[0,1]	[0,1]

Key Moments - 3 Insights

Why do we check for complement in the map before adding the current number?

Checking complement first ensures we don't use the same element twice. See step 3 in execution_table where complement 2 is found before adding 7.

What happens if no two numbers add up to the target?

The loop finishes without returning. The function returns an empty result as shown in the exit_note after step 4.

Why do we store number:index in the hash map?

We store indices to return the positions of the two numbers. The map helps find the complement's index quickly, as shown in variable_tracker for hash_map.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the hash map state?

A {2:0}

B {}

C {7:1}

D {2:1}

💡 Hint

Check the 'Hash Map State' column at step 2 in execution_table.

At which step does the complement get found in the hash map?

A Step 1

B Step 3

C Step 2

D Step 4

💡 Hint

Look at the 'Action' column in execution_table where complement is found.

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

A Complement found and return indices

B Loop ends immediately

C Complement not found, add current number to map

D Error occurs

💡 Hint

Think about complement calculation and map lookup in execution_table step 3.

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, add current number to map
- Runs in O(n) time with O(n) space

Full Transcript

The Two Sum problem is solved by scanning the array once and using a hash map to store numbers and their indices. For each number, we calculate the complement needed to reach the target. We check if this complement is already in the map. If found, we return the 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.

Practice

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

easy

A. To store numbers and their indices for quick lookup

B. To sort the array before searching

C. To store the sum of all pairs

D. To reverse the array elements

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: Explain why quick lookup is needed

   Quick lookup helps find if the complement (target - current number) exists without scanning the entire array.

3. Final Answer:

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

4. Quick Check:

   Hash map = quick index lookup [OK]

Hint: Hash map stores values for instant complement search [OK]

Common Mistakes:

• Thinking hash map sorts the array
• Confusing hash map with storing sums
• Assuming hash map reverses elements

2. Which of the following C++ code snippets correctly declares the hash map used in the Two Sum problem to store integer keys and values?

easy

A. std::map<int> map;

B. std::unordered_map map;

C. std::unordered_map<int> map;

D. std::vector map;

Solution

1. Step 1: Identify correct hash map syntax

   std::unordered_map declares a hash map with int keys and int values.

2. Step 2: Explain why others are incorrect

   std::map<int> lacks value type; std::unordered_map<int> lacks value type; std::vector is invalid syntax.

3. Final Answer:

   std::unordered_map<int, int> map; -> Option B

4. Quick Check:

   Correct hash map syntax = std::unordered_map<int, int> [OK]

Hint: Use std::unordered_map<key, value> for hash maps in C++ [OK]

Common Mistakes:

• Omitting value type in map declaration
• Using std::vector instead of map
• Confusing std::map and std::unordered_map syntax

3. What will be the output of the following C++ code snippet for the input array nums = {2, 7, 11, 15} and target = 9?

std::vector<int> twoSum(std::vector<int>& nums, int target) {
    std::unordered_map<int, int> map;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (map.find(complement) != map.end()) {
            return {map[complement], i};
        }
        map[nums[i]] = i;
    }
    return {};
}

int main() {
    auto result = twoSum({2, 7, 11, 15}, 9);
    for (int i : result) std::cout << i << " ";
}

medium

A. [1 0]

B. [2 3]

C. [0 1]

D. No output

Solution

1. Step 1: Trace the loop and map updates

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

2. Step 2: Return indices of complement and current

   Return {0,1} which prints as "0 1".

3. Final Answer:

   [0 1] -> Option C

4. Quick Check:

   Indices of 2 and 7 = 0 and 1 [OK]

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

Common Mistakes:

• Returning indices in wrong order
• Not checking complement before insertion
• Confusing values with indices

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

std::vector<int> twoSum(std::vector<int>& nums, int target) {
    std::unordered_map<int, int> map;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (map.find(complement) != map.end()) {
            return {i, map[complement]};
        }
        map[nums[i]] = i;
    }
    return {};
}

medium

A. Swap the return indices to {map[complement], i}

B. Change unordered_map to map

C. Insert nums[i] into map before checking complement

D. Return empty vector immediately

Solution

1. Step 1: Analyze the return statement order

   The function returns {i, map[complement]} but correct order is {map[complement], i} to match indices.

2. Step 2: Explain why swapping fixes the bug

   Swapping ensures the first index is of complement and second is current index, matching problem requirement.

3. Final Answer:

   Swap the return indices to {map[complement], i} -> Option A

4. Quick Check:

   Correct index order = complement index, current index [OK]

Hint: Return complement index first, then current index [OK]

Common Mistakes:

• Returning indices in wrong order
• Inserting before checking complement
• Changing map type unnecessarily

5. Given the input array nums = {3, 3, 4, 5} and target = 6, what will the classic Two Sum hash solution return and why?

std::vector<int> twoSum(std::vector<int>& nums, int target) {
    std::unordered_map<int, int> map;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (map.find(complement) != map.end()) {
            return {map[complement], i};
        }
        map[nums[i]] = i;
    }
    return {};
}

hard

A. Empty vector because no two numbers sum to 6

B. [2 3] because 4 and 5 sum to 9, not 6

C. [1 0] because indices are reversed

D. [0 1] because first 3 and second 3 sum to 6

Solution

1. Step 1: Trace the loop with duplicates

   At i=0, map empty, insert (3,0). At i=1, complement=6-3=3 found at index 0.

2. Step 2: Return indices of first and second 3

   Return {0,1} because nums[0] + nums[1] = 3 + 3 = 6.

3. Final Answer:

   [0 1] because first 3 and second 3 sum to 6 -> Option D

4. Quick Check:

   Duplicates allowed, indices 0 and 1 sum to target [OK]

Hint: Duplicates can form valid pairs if sum matches target [OK]

Common Mistakes:

• Ignoring duplicates in map
• Assuming no pair sums to target
• Returning indices in wrong order