Two Sum Problem Classic Hash Solution in DSA Go - 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 nil

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

Execution Sample

DSA Go

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for i, num := range nums {
        comp := target - num
        if j, ok := m[comp]; ok {
            return []int{j, i}
        }
        m[num] = i
    }
    return nil
}

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

Execution Table

Step	Operation	Current Number (num)	Complement (comp)	Hash Map State	Action	Result
1	Start loop	-	-	{}	Initialize empty map	-
2	i=0, num=2	2	7	{}	Check if 7 in map: No	Add 2:0 to map
3	i=1, num=7	7	2	{2:0}	Check if 2 in map: Yes	Return indices [0,1]
4	End	-	-	-	-	Found pair, stop

💡 At step 3, complement 2 found in map, so indices [0,1] returned and loop ends.

Variable Tracker

Variable	Start	After Step 2	After Step 3	Final
m (map)	{}	{2:0}	{2:0}	{2:0}
i (index)	-	0	1	1
num (current number)	-	2	7	7
comp (complement)	-	7	2	2

Key Moments - 3 Insights

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

Because if we add the current number first, we might find the same number as complement and return the same index twice. Checking first ensures we find a different number's index as complement (see execution_table step 3).

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

The loop finishes without returning, and the function returns nil as shown in the code and exit_note, meaning no pair found.

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

Because we want to quickly check if a needed complement number exists and get its index to return. The map lets us find indices by number in O(1) time.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the state of the hash map after processing num=2?

A {}

B {"2":0}

C {"7":0}

D {"2":1}

💡 Hint

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

At which step does the function find the pair that sums to the target?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Action' and 'Result' columns in execution_table to see when indices are returned.

If the input array was [3, 3] and target 6, what would the hash map contain after processing the first element?

A {"3":0}

B {}

C {"6":0}

D {"3":1}

💡 Hint

Refer to variable_tracker and execution_table logic for adding current number to map.

Concept Snapshot

Two Sum Classic Hash Solution:
- Use a map to store number:index
- For each number, compute complement = target - number
- Check if complement in map:
  - If yes, return indices
  - Else, add number:index 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 remember 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 yes, we return the pair of indices immediately. If not, we add the current number and its index to the map and continue. If no pair is found by the end, we return nil. This approach is efficient because it avoids nested loops and uses quick lookups in the map.

Practice

1. What is the main idea behind the Two Sum Problem Classic Hash Solution?

easy

A. Use a hash map 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 goal

   The goal is to find two numbers in the array that add up to a target value.

2. Step 2: Use a hash map for efficient lookup

   By storing each number and its index in a hash map, we can check if the complement (target - current number) exists quickly.

3. Final Answer:

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

4. Quick Check:

   Hash map lookup = fast pair finding [OK]

Hint: Use a hash map to find complements quickly [OK]

Common Mistakes:

• Trying to use nested loops which is slower
• Sorting the array which is unnecessary here
• Not storing indices with numbers

2. Which of the following Go code snippets correctly initializes a hash map to store integers as keys and values?

easy

A. var m map[int]int

B. m := map[int]int

C. m := make(map[int]int)

D. m := map[int]int(make())

Solution

1. Step 1: Recall Go map initialization syntax

   Maps in Go are initialized using the built-in make function like make(map[keyType]valueType).

2. Step 2: Identify correct syntax

   m := make(map[int]int) uses make(map[int]int) which is the correct way to create an empty map with int keys and int values.

3. Final Answer:

   m := make(map[int]int) -> Option C

4. Quick Check:

   make(map[int]int) = correct map init [OK]

Hint: Use make(map[key]value) to create maps in Go [OK]

Common Mistakes:

• Using var without make causes nil map
• Incorrect syntax like map[int]int(make())
• Using empty braces without make in some contexts

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

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for i, num := range nums {
        if j, ok := m[target-num]; ok {
            return []int{j, i}
        }
        m[num] = i
    }
    return nil
}

fmt.Println(twoSum([]int{2, 7, 11, 15}, 9))

medium

A. [1 0]

B. [0 1]

C. [2 3]

D. nil

Solution

1. Step 1: Trace the loop and map updates

   At i=0, num=2, map is empty, so store m[2]=0.
   At i=1, num=7, check if m[9-7=2] exists, yes at index 0.
   Return [0,1].

2. Step 2: Confirm returned indices

   The function returns indices of numbers 2 and 7 which sum to 9, so output is [0 1].

3. Final Answer:

   [0 1] -> Option B

4. Quick Check:

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

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

Common Mistakes:

• Returning indices in wrong order
• Not checking map before insertion
• Returning nil when pair exists

4. Identify the error in the following Go code for the Two Sum problem:

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for i, num := range nums {
        if j, ok := m[num-target]; ok {
            return []int{j, i}
        }
        m[num] = i
    }
    return nil
}

medium

A. The complement calculation should be target - num, not num - target

B. The map should store num + target as key

C. The map initialization is incorrect

D. The return statement should return nil earlier

Solution

1. Step 1: Analyze complement calculation

   The complement to find is target - current number, not num - target, because we want a number that adds with num to target.

2. Step 2: Identify the fix

   Change m[num-target] to m[target-num] to correctly check for the complement in the map.

3. Final Answer:

   The complement calculation should be target - num, not num - target -> Option A

4. Quick Check:

   Complement = target - num [OK]

Hint: Complement = target minus current number [OK]

Common Mistakes:

• Swapping target and num in complement
• Incorrect map initialization
• Returning nil too early

5. Given the input array nums = [3, 3, 4, 2] and target 6, what will the Two Sum Classic Hash Solution return?
Consider the code below:

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for i, num := range nums {
        if j, ok := m[target-num]; ok {
            return []int{j, i}
        }
        m[num] = i
    }
    return nil
}

medium

A. nil

B. [1 2]

C. [2 3]

D. [0 1]

Solution

1. Step 1: Trace the loop with given input

   i=0, num=3, map empty, store m[3]=0.
   i=1, num=3, check m[6-3=3], found at index 0, return [0,1].

2. Step 2: Confirm returned indices

   Indices 0 and 1 correspond to values 3 and 3 which sum to 6, so output is [0 1].

3. Final Answer:

   [0 1] -> Option D

4. Quick Check:

   3 + 3 = 6 at indices [0 1] [OK]

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

Common Mistakes:

• Assuming different pairs without checking map
• Returning nil when pair exists
• Confusing indices order