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

↓

Move to next number

↓

If end reached without match

→Return no solution

We scan the array once, storing numbers and their indices in a hash 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 C

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
  // hash map stores number -> index
  // This is a placeholder; actual hash map implementation needed
  for (int i = 0; i < numsSize; i++) {
    int complement = target - nums[i];
    if (hash_map_contains(complement)) {
      *returnSize = 2;
      int* result = malloc(2 * sizeof(int));
      result[0] = hash_map_get(complement);
      result[1] = i;
      return result;
    }
    hash_map_add(nums[i], i);
  }
  *returnSize = 0;
  return NULL;
}

This code finds two numbers in the array that add up to the target by using a hash map for quick lookups.

Execution Table

Step	Operation	Current Number (nums[i])	Complement (target - nums[i])	Hash Map State (number:index)	Action	Result / Visual State
1	Start	-	-	{}	Initialize empty hash map	Hash map empty
2	Process nums[0]	2	7	{}	Check complement 7 in map? No	Add 2:0 to map -> {2:0}
3	Process nums[1]	7	2	{2:0}	Check complement 2 in map? Yes	Found pair (0,1) because 2 + 7 = 9
4	Return	-	-	{2:0}	Return indices (0,1)	Solution found, stop

💡 At step 3, complement 2 found in hash map, so pair (0,1) returned.

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}

Key Moments - 2 Insights

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

Because if we add the current number first, we might find the same number as complement and incorrectly pair it with itself. Checking first ensures we only pair different indices. See step 3 in execution_table.

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

The loop finishes without finding a complement in the hash map, so the function returns no solution. This is shown by the exit_note after all steps.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the hash map state after processing nums[0]?

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 algorithm find the solution?

A Step 3

B Step 1

C Step 2

D Step 4

💡 Hint

Look for the step where complement is found in the hash map in execution_table.

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

A Complement found, solution returned

B Algorithm stops immediately

C Complement not found, current number added to map

D Hash map cleared

💡 Hint

Think about complement calculation and hash map lookup at step 3 in 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, 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 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 hash map. If yes, we return the pair of indices immediately. If not, we add the current number and its index to the hash map and continue. This approach ensures we find the solution 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 all pairs of numbers

B. To sort the array before searching

C. To store numbers and their indices for quick lookup

D. To reverse the array elements

Solution

1. Step 1: Understand the role of hash map in Two Sum

   The hash map stores each number as a key and its index as the value for quick lookup.

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 again.

3. Final Answer:

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

4. Quick Check:

   Hash map = quick lookup [OK]

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

Common Mistakes:

• Thinking hash map sorts the array
• Assuming hash map stores all pairs
• Confusing hash map with array reversal

2. Which of the following is the correct syntax to declare a hash map (dictionary) in C for the Two Sum problem?

easy

A. unordered_map hashmap;

B. int hashmap[1000];

C. map hashmap = new map();

D. dict hashmap = {};

Solution

1. Step 1: Identify C++ STL syntax for hash map

   In C++, unordered_map is used for hash maps with integer keys and values.

2. Step 2: Check other options for correctness

   int hashmap[1000]; is a fixed-size array, not a hash map. map hashmap = new map(); is invalid syntax. dict hashmap = {}; is Python syntax.

3. Final Answer:

   unordered_map hashmap; -> Option A

4. Quick Check:

   unordered_map = hash map in C++ [OK]

Hint: Use unordered_map for hash map in C++ [OK]

Common Mistakes:

• Using array instead of hash map
• Confusing Python or Java syntax with C++
• Incorrect map declaration syntax

3. What will be the output of the following code snippet for input nums = [2, 7, 11, 15], target = 9?

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    unordered_map map;
    for (int i = 0; i < numsSize; i++) {
        int complement = target - nums[i];
        if (map.find(complement) != map.end()) {
            int* result = (int*)malloc(2 * sizeof(int));
            result[0] = map[complement];
            result[1] = i;
            *returnSize = 2;
            return result;
        }
        map[nums[i]] = i;
    }
    *returnSize = 0;
    return NULL;
}

medium

A. [1, 0]

B. [0, 1]

C. [2, 3]

D. NULL

Solution

1. Step 1: Trace the loop and hash map insertions

   At i=0, map = {2:0}. At i=1, complement = 9-7=2 found in map at index 0.

2. Step 2: Return indices of complement and current number

   Return [0,1] as the pair that sums to 9.

3. Final Answer:

   [0, 1] -> Option B

4. Quick Check:

   nums[0]+nums[1] = 2+7 = 9 [OK]

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

Common Mistakes:

• Returning indices in wrong order
• Not checking complement before insertion
• Returning NULL when pair exists

4. Identify the bug in this Two Sum hash map solution snippet:

for (int i = 0; i < numsSize; i++) {
    map[nums[i]] = i;
    int complement = target - nums[i];
    if (map.find(complement) != map.end()) {
        return {map[complement], i};
    }
}

medium

A. Loop should start from i = 1

B. map should store complement instead of current number

C. Return statement syntax is invalid in C

D. Complement check should happen before inserting current number

Solution

1. Step 1: Analyze order of operations in loop

   Current number is inserted before checking complement, causing false positive when complement equals current number.

2. Step 2: Correct order to check complement before insertion

   Check if complement exists in map first, then insert current number to avoid matching with itself.

3. Final Answer:

   Complement check should happen before inserting current number -> Option D

4. Quick Check:

   Check complement before insert [OK]

Hint: Check complement before adding current number to map [OK]

Common Mistakes:

• Inserting before checking complement
• Wrong return syntax in C
• Starting loop from wrong index

5. Given an array nums = [3, 3, 4, 5] and target = 6, what will the Two Sum hash map solution return and why?

hard

A. [0, 1] because nums[0] + nums[1] = 3 + 3 = 6

B. [2, 3] because nums[2] + nums[3] = 4 + 5 = 9

C. NULL because no two numbers sum to 6

D. [1, 0] because indices order is reversed

Solution

1. Step 1: Trace the hash map insertions and complement checks

   At i=0, map = {3:0}. At i=1, complement = 6-3=3 found at index 0.

2. Step 2: Return indices of the first valid pair

   Return [0,1] as the pair that sums to 6.

3. Final Answer:

   [0, 1] because nums[0] + nums[1] = 3 + 3 = 6 -> Option A

4. Quick Check:

   3 + 3 = 6 [OK]

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

Common Mistakes:

• Ignoring duplicate values
• Returning wrong indices order
• Assuming no pair exists when duplicates present