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

Concept Flow - Two Sum Problem Classic Hash Solution

Start with empty hash map

↓

Iterate over array elements

↓

Calculate complement = target - current element

↓

Check if complement in hash map?

Yes→Return indices

No↓

Add current element and index to hash map

↓

Repeat until found or end

↓

If no pair found, return empty

We scan the array once, storing elements in a hash map. For each element, we check if its complement exists in the map to find the pair.

Execution Sample

DSA Typescript

function twoSum(nums: number[], target: number): number[] {
  const map = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) return [map.get(complement)!, i];
    map.set(nums[i], i);
  }
  return [];
}

This code finds two indices in the array whose values add up to the target using a hash map.

Execution Table

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

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

Variable Tracker

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

Key Moments - 3 Insights

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

Because we want to find if a previously seen number pairs with the current number to reach the target. Checking first ensures we don't miss pairs where the complement appeared earlier (see step 4 in execution_table).

What happens if the array has duplicate numbers?

The map stores the latest index for each number. If a complement is found, it returns the pair immediately. This works correctly because we check complement before adding current number (see steps 2-4).

Why do we return immediately when we find the complement?

Because the problem asks for any one valid pair. Once found, continuing is unnecessary (step 4 shows immediate return).

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the complement calculated for current number 2?

A 7

B 2

C 9

D 0

💡 Hint

Check the 'Complement' column at step 2 in execution_table.

At which step does the algorithm find the complement in the map and return the result?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look for 'Complement found in map' in the 'Action' column.

If the input array was [3,3] and target 6, what would the map contain before returning?

A {3:1}

B {3:0}

C {}

D {6:0}

💡 Hint

Refer to variable_tracker for how map updates before return.

Concept Snapshot

Two Sum Classic Hash Solution:
- Use a hash map to store number:index pairs.
- For each number, compute complement = target - number.
- Check if complement exists in map before adding current number.
- If found, return indices immediately.
- 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 seen so far. 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 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 Two Sum problem classic solution?

easy

A. To store the sum of all pairs

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

   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 to 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 stores number:index = A [OK]

Hint: Hash map stores values for instant complement check [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 TypeScript code snippets correctly initializes an empty hash map for the Two Sum problem?

easy

A. const map = new Map();

B. const map = {};

C. const map = new Array();

D. const map = new Set();

Solution

1. Step 1: Identify correct hash map initialization

   In TypeScript, new Map<number, number>() creates a map with number keys and values.

2. Step 2: Explain why other options are incorrect

   {} is an object but lacks type safety; new Array() is an array, not a map; new Set() stores unique values, not key-value pairs.

3. Final Answer:

   const map = new Map<number, number>(); -> Option A

4. Quick Check:

   Use Map<number, number> for hash map [OK]

Hint: Use Map<number, number> for key-value pairs [OK]

Common Mistakes:

• Using Set instead of Map
• Using Array instead of Map
• Using plain object without type safety

3. What will be the output of the following TypeScript code for the input array [2, 7, 11, 15] and target 9?

function twoSum(nums: number[], target: number): number[] {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      return [map.get(complement)!, i];
    }
    map.set(nums[i], i);
  }
  return [];
}

console.log(twoSum([2, 7, 11, 15], 9));

medium

A. [1, 2]

B. []

C. [2, 3]

D. [0, 1]

Solution

1. Step 1: Trace the loop and map updates

   i=0: map={}, complement=9-2=7, map.has(7)? No, map.set(2,0).
   i=1: complement=9-7=2, map.has(2)? Yes, index=0, return [0,1].

2. Step 2: Confirm returned indices

   Indices 0 and 1 correspond to numbers 2 and 7 which sum to 9.

3. Final Answer:

   [0, 1] -> Option D

4. Quick Check:

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

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

Common Mistakes:

• Returning values instead of indices
• Not checking map before insertion
• Returning empty array incorrectly

4. Identify the bug in this TypeScript Two Sum implementation:

function twoSum(nums: number[], target: number): number[] {
  const map = new Map();
  for (let i = 0; i <= nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      return [map.get(complement)!, i];
    }
    map.set(nums[i], i);
  }
  return [];
}

medium

A. map.set should be called before checking complement

B. Loop condition should be < instead of <=

C. Return statement should return values instead of indices

D. Complement calculation is incorrect

Solution

1. Step 1: Analyze loop condition

   The loop uses i <= nums.length, which causes out-of-bounds access at last iteration.

2. Step 2: Correct loop condition

   Change to i < nums.length to avoid accessing undefined element.

3. Final Answer:

   Loop condition should be < instead of <= -> Option B

4. Quick Check:

   Loop must stay within array bounds [OK]

Hint: Use < not <= for array index loops [OK]

Common Mistakes:

• Off-by-one error in loop condition
• Swapping order of map.set and map.has
• Returning values instead of indices

5. Given the input array [3, 3, 4, 5] and target 6, what will the Two Sum classic hash solution return?

function twoSum(nums: number[], target: number): number[] {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      return [map.get(complement)!, i];
    }
    map.set(nums[i], i);
  }
  return [];
}

console.log(twoSum([3, 3, 4, 5], 6));

hard

A. [0, 1]

B. [1, 2]

C. [2, 3]

D. []

Solution

1. Step 1: Trace the loop and map updates with duplicates

   i=0: map={}, complement=6-3=3, map.has(3)? No, map.set(3,0).
   i=1: complement=6-3=3, map.has(3)? Yes, index=0, return [0,1].

2. Step 2: Confirm correct pair with duplicates

   Even with duplicates, first pair indices 0 and 1 sum to 6.

3. Final Answer:

   [0, 1] -> Option A

4. Quick Check:

   Duplicates handled, indices [0,1] sum to target [OK]

Hint: Duplicates allowed; first matching pair returned [OK]

Common Mistakes:

• Ignoring duplicates and returning wrong indices
• Returning empty array incorrectly
• Confusing values with indices