Two Sum Problem Classic Hash Solution in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Two Sum problem classic hash solution?

Use a hash map (object) to store numbers and their indices while iterating. For each number, check if the complement (target - current number) exists in the map. If yes, return the pair of indices.

beginner

Why do we use a hash map in the Two Sum problem?

A hash map allows quick lookup (in constant time) to check if the complement number exists, making the solution efficient (O(n) time).

intermediate

What is the time complexity of the classic hash solution for Two Sum?

O(n), where n is the number of elements in the array, because we do a single pass and constant time lookups.

beginner

What happens if no two numbers add up to the target in the Two Sum problem?

The function returns an empty array, indicating no valid pair was found.

beginner

Explain the role of the complement in the Two Sum hash solution.

The complement is the number needed to add to the current number to reach the target. Checking if the complement exists in the hash map helps find the pair quickly.

In the Two Sum hash solution, what data structure is primarily used to store numbers and their indices?

A Hash map (object)

B Array

C Linked list

D Stack

The hash map allows quick lookup of complements to find pairs efficiently.

What is the time complexity of the Two Sum classic hash solution?

A O(n^2)

B O(n log n)

C O(n)

D O(log n)

The solution uses a single pass with constant time lookups, resulting in O(n) time.

What does the 'complement' mean in the Two Sum problem?

A The number needed to reach the target when added to the current number

B The current number itself

C The index of the current number

D The target number

The complement is target minus the current number, needed to find the pair.

If the input array is [2, 7, 11, 15] and target is 9, what indices does the Two Sum solution return?

A []

B [1, 2]

C [2, 3]

D [0, 1]

2 + 7 = 9, so indices 0 and 1 are returned.

What should the Two Sum function return if no pair sums to the target?

A The first element

B An empty array

C The entire array

D The target number

Returning an empty array indicates no valid pair found.

Describe step-by-step how the Two Sum classic hash solution finds the pair of indices.

Think about how you use a dictionary to remember numbers you have seen.

Explain why using a hash map improves the efficiency of the Two Sum problem compared to a nested loop approach.

Compare checking for complements quickly versus checking all pairs.

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