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

Concept Flow - Two Sum Problem Classic Hash Solution

Start with empty hash map

↓

Iterate over 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 None

We scan the list 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 of indices.

Execution Sample

DSA Python

def two_sum(nums, target):
    hashmap = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hashmap:
            return [hashmap[complement], i]
        hashmap[num] = i
    return None

This code finds two numbers in 'nums' that add up to 'target' and returns their indices.

Execution Table

Step	Operation	Current Number (num)	Index (i)	Complement (target - num)	Hash Map State	Action	Result
1	Start iteration	-	-	-	{}	Initialize empty hash map	-
2	Check complement	2	0	7	{}	7 not in hash map	Add 2:0 to hash map
3	Add to hash map	2	0	7	{2:0}	-	-
4	Check complement	7	1	2	{2:0}	2 found in hash map	Return [0,1]
5	End	-	-	-	{2:0}	Pair found, stop	[0,1]

💡 Complement found in hash map at step 4, so indices [0,1] returned.

Variable Tracker

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

Key Moments - 3 Insights

Why do we check if the complement is in the hash map before adding the current number?

Because if we add the current number first, we might match it with itself. Checking first ensures we only find pairs with different indices, as shown in execution_table step 4 where complement 2 is found before adding 7.

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

The loop finishes without returning, so the function returns None (not shown in this example). The hash map ends up containing all numbers with their indices, but no complement match is found.

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

Because we need to quickly check if a complement number exists and retrieve its index to return the pair. The hash map allows O(1) lookup by number.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the value of 'complement'?

A 2

B 7

C 0

D 1

💡 Hint

Check the 'Complement (target - num)' column at step 4 in execution_table.

At which step does the hash map first contain the key 2?

A Step 2

B Step 3

C Step 1

D Step 4

💡 Hint

Look at the 'Hash Map State' column to see when {2:0} appears.

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

A Complement 3 found in hash map

B Complement 2 found in hash map

C Complement 3 not found in hash map

D Complement 7 found in hash map

💡 Hint

Think about how complement is calculated and check hash map contents in variable_tracker.

Concept Snapshot

Two Sum Classic Hash Solution:
- Use a hash map to store numbers and their indices.
- For each number, compute complement = target - number.
- Check if complement is in hash map.
- If yes, return indices.
- Else, add current number and index to hash map.
- Runs in O(n) time with one pass.

Full Transcript

The Two Sum problem finds two numbers in a list that add up to a target. This classic hash solution uses a hash map to store numbers and their indices as we scan the list once. For each number, we calculate the complement needed to reach the target. We check if this complement is already in the hash map. If found, we return the pair of indices immediately. Otherwise, we add the current number and its index to the hash map and continue. This approach avoids nested loops and runs efficiently in linear time. The execution table shows step-by-step how the hash map changes and when the pair is found.

Practice

1. What is the main idea behind the classic hash solution for the Two Sum Problem?

easy

A. Use a dictionary to store numbers and their indices for quick lookup

B. Sort the array and use two pointers to find the sum

C. Use nested loops to check every pair of numbers

D. Use recursion to find pairs that add up to the target

Solution

1. Step 1: Understand the problem requirement

   The Two Sum problem asks to find two numbers in an array that add up to a target value.

2. Step 2: Explain the hash solution approach

   Using a dictionary (hash map) allows storing each number's index and checking if the complement (target - current number) exists quickly.

3. Final Answer:

   Use a dictionary to store numbers and their indices for quick lookup -> Option A

4. Quick Check:

   Hash map lookup = fast pair finding [OK]

Hint: Use a dictionary to find complements quickly [OK]

Common Mistakes:

• Trying to sort the array which changes indices
• Using nested loops causing slow performance
• Not storing indices, only values

2. Which of the following is the correct syntax to check if a key exists in a Python dictionary named seen?

easy

A. if key exists in seen:

B. if key in seen:

C. if seen.has_key(key):

D. if key inside seen:

Solution

1. Step 1: Recall Python dictionary membership syntax

   In Python, to check if a key exists in a dictionary, use the syntax if key in dict:.

2. Step 2: Identify correct option

   if key in seen: uses the correct syntax. if key exists in seen: and D are invalid syntax. if seen.has_key(key): is legacy and removed in Python 3.

3. Final Answer:

   if key in seen: -> Option B

4. Quick Check:

   Python dict key check = if key in dict [OK]

Hint: Use 'in' keyword to check dictionary keys [OK]

Common Mistakes:

• Using outdated has_key() method
• Writing invalid syntax like 'exists in'
• Confusing keys with values

3. What will be the output of the following code?

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

print(two_sum([2, 7, 11, 15], 9))

medium

A. [0, 1]

B. [1, 2]

C. [2, 3]

D. []

Solution

1. Step 1: Trace the loop and dictionary updates

   Iteration 0: num=2, complement=7, seen={}, complement not in seen, add 2:0.
   Iteration 1: num=7, complement=2, complement 2 in seen at index 0, return [0,1].

2. Step 2: Determine returned indices

   The function returns indices [0,1] where nums[0]+nums[1]=2+7=9.

3. Final Answer:

   [0, 1] -> Option A

4. Quick Check:

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

Hint: Check complement in dict before adding current number [OK]

Common Mistakes:

• Returning values instead of indices
• Adding current number before checking complement
• Returning empty list incorrectly

4. The following code tries to solve the Two Sum problem but has a bug. What is the bug?

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        if num in seen:
            return [seen[num], i]
        complement = target - num
        seen[complement] = i
    return []

medium

A. It does not check for complement in dictionary

B. It returns indices in wrong order

C. It stores complement as key instead of the number itself

D. It uses enumerate incorrectly

Solution

1. Step 1: Analyze dictionary key storage

   The code stores complement as key with current index, but it should store the number as key to check complement later.

2. Step 2: Identify impact of wrong key storage

   Because complement is stored as key, the lookup for num in seen fails to find correct pairs, causing wrong or no results.

3. Final Answer:

   It stores complement as key instead of the number itself -> Option C

4. Quick Check:

   Store number as key, not complement [OK]

Hint: Store numbers as keys, check for complement [OK]

Common Mistakes:

• Swapping complement and number keys
• Returning indices before checking complement
• Not using enumerate properly

5. Given the list nums = [3, 3, 4, 5] and target = 6, what will the classic hash solution return?
Consider the code:

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

print(two_sum(nums, target))

hard

A. []

B. [1, 2]

C. [2, 3]

D. [0, 1]

Solution

1. Step 1: Trace the loop with duplicates

   Iteration 0: num=3, complement=3, seen={}, complement not in seen, add 3:0.
   Iteration 1: num=3, complement=3, complement 3 in seen at index 0, return [0,1].

2. Step 2: Understand duplicate handling

   The solution correctly finds the two 3's at indices 0 and 1 that sum to 6.

3. Final Answer:

   [0, 1] -> Option D

4. Quick Check:

   Two 3's indices = [0, 1] [OK]

Hint: Duplicates allowed; first pair found is returned [OK]

Common Mistakes:

• Ignoring duplicates and returning empty list
• Returning wrong indices due to overwriting
• Assuming no pair exists when duplicates present