Why Two Sum Problem Classic Hash Solution in DSA Javascript?

The Big Idea

Discover how a simple table can save you from endless guessing and speed up your search!

The Scenario

Imagine you have a list of prices for items in a store, and you want to find two items that add up to exactly the amount of money you have in your wallet.

You try to check every possible pair by hand, adding each pair to see if it matches your money.

The Problem

Checking every pair manually takes a lot of time, especially if the list is long.

You might miss pairs or repeat checks, making it slow and frustrating.

The Solution

The Two Sum Classic Hash Solution uses a simple table to remember what numbers you've seen.

Instead of checking all pairs, you look up if the number needed to reach your target is already in the table.

This way, you find the answer quickly without repeating work.

Before vs After

✗ Before

for (let i = 0; i < nums.length; i++) {
  for (let j = i + 1; j < nums.length; j++) {
    if (nums[i] + nums[j] === target) return [i, j];
  }
}

✓ After

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);
}

What It Enables

This method lets you find pairs that add up to a target in just one pass, making your code fast and efficient.

Real Life Example

When shopping online, the website can quickly suggest two products that fit your budget by using this method behind the scenes.

Key Takeaways

Manual pair checking is slow and repeats work.

Using a hash table remembers seen numbers for quick lookup.

This approach finds pairs in one pass, saving time.

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