Two Sum Problem Classic Hash Solution in DSA Javascript - 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 for next element

↓

If no pair found, return no solution

We scan the array once, storing elements in a hash map. For each element, we check if its complement to reach the target exists in the map. If yes, we return the pair indices.

Execution Sample

DSA Javascript

function twoSum(nums, target) {
  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 [];
}

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 Index (i)	Current Number	Complement	Hash Map State	Action	Result
1	Initialize	-	-	-	{}	Create empty map	-
2	Iteration start	0	2	7	{}	Check if 7 in map	No
3	Add to map	0	2	7	{2:0}	Add 2 with index 0	-
4	Iteration start	1	7	2	{2:0}	Check if 2 in map	Yes
5	Return result	1	7	2	{2:0}	Return indices [0,1]	[0,1]

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

Variable Tracker

Variable	Start	After Step 3	After Step 5 (End)
i	-	0	1
current number	-	2	7
complement	-	7	2
map	{}	{2:0}	{2:0}

Key Moments - 3 Insights

Why do we check if 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 if the array has duplicate numbers? Will the map overwrite indices?

Yes, the map stores the latest index for a number. But since we check for complement before adding current number, the first valid pair is found correctly (see steps 2-5).

Why do we return immediately when complement is found?

Because the problem asks for one valid pair. Once found, no need to continue. This is shown at step 5 where function returns indices.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the complement calculated?

A 9

B 7

C 2

D 0

💡 Hint

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

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

A Step 1

B Step 3

C Step 2

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 would be 3 and not found in map

B Complement would be 3 and found in map

C Complement would be 2 and found in map

D Complement would be 7 and found in map

💡 Hint

Calculate complement = target - current number at step 4 and check map contents.

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 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 store numbers and their indices. For each element, 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. Otherwise, we add the current number and its index to the map and continue. This approach ensures we find the first valid pair efficiently. The execution table shows each step, including map state and actions. Key moments clarify why we check complement before adding and how duplicates are handled. The visual quiz tests understanding of complement calculation, map updates, and behavior with different targets.

Practice

1. What is the main purpose of using a hash map in the Two Sum problem classic 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 again.

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 check [OK]

Common Mistakes:

• Thinking hash map sorts the array
• Storing sums instead of indices
• Using hash map to reverse array

2. Which of the following is the correct syntax to check if a key exists in a JavaScript Map during the Two Sum solution?

easy

A. map.has(key)

B. map.contains(key)

C. map.exists(key)

D. map.includes(key)

Solution

1. Step 1: Recall JavaScript Map method for key check

   The correct method to check if a key exists in a Map is has().

2. Step 2: Verify other options are invalid

   Methods contains(), exists(), and includes() do not exist on Map objects.

3. Final Answer:

   map.has(key) -> Option A

4. Quick Check:

   Map key check = has() [OK]

Hint: Use map.has(key) to check existence [OK]

Common Mistakes:

• Using contains() instead of has()
• Using includes() which is for arrays
• Trying to access keys directly

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

function twoSum(nums, target) {
  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. [2, 3]

B. [1, 2]

C. [0, 1]

D. []

Solution

1. Step 1: Trace the loop and map updates

   At i=0, map is empty, store (2,0). At i=1, complement=9-7=2, map has 2 at index 0.

2. Step 2: Return indices when complement found

   Return [0,1] as indices of numbers 2 and 7 that sum to 9.

3. Final Answer:

   [0, 1] -> Option C

4. Quick Check:

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

Hint: Return indices when complement found in map [OK]

Common Mistakes:

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

4. Identify the bug in this Two Sum solution code:

function twoSum(nums, target) {
  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. Complement calculation is incorrect

B. map.set should be called before checking complement

C. Return statement should return values, not indices

D. Loop condition should be i < nums.length, not i <= nums.length

Solution

1. Step 1: Check loop boundary

   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 i < nums.length, not i <= nums.length -> Option D

4. Quick Check:

   Loop boundary off-by-one error [OK]

Hint: Use i < length to avoid out-of-bounds error [OK]

Common Mistakes:

• Using <= instead of < in loop
• Swapping map.set and complement check order
• Returning values instead of indices

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

function twoSum(nums, target) {
  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 [];
}

hard

A. [1, 2]

B. [0, 1]

C. [2, 3]

D. []

Solution

1. Step 1: Trace the loop with duplicates

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

2. Step 2: Return indices of first matching pair

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

3. Final Answer:

   [0, 1] -> Option B

4. Quick Check:

   Duplicates handled, first pair indices returned [OK]

Hint: Duplicates allowed; return first valid pair indices [OK]

Common Mistakes:

• Returning later pair indices instead of first
• Ignoring duplicates in map
• Returning values instead of indices