Two Sum Problem Classic Hash Solution in DSA Javascript

Mental Model

We want to find two numbers that add up to a target by remembering numbers we've seen before.

Analogy: Imagine you have a list of prices and a gift card. You check each price and remember it. When you see a new price, you check if the gift card minus this price is something you already saw.

nums: [2] -> [7] -> [11] -> [15] -> null
hash: {} (empty at start)

Dry Run Walkthrough

Input: nums: [2, 7, 11, 15], target: 9

Goal: Find two indices where the numbers add up to 9

Step 1: Check first number 2, look for 9 - 2 = 7 in hash (not found), add 2 with index 0 to hash

nums: 2 -> 7 -> 11 -> 15 -> null
hash: {2:0}

Why: We store 2 to check if future numbers can pair with it

Step 2: Check second number 7, look for 9 - 7 = 2 in hash (found at index 0), return indices [0,1]

nums: 2 -> [7] -> 11 -> 15 -> null
hash: {2:0}

Why: Found a pair that sums to target, so we stop

Result:

nums: 2 -> 7 -> 11 -> 15 -> null
Answer: indices [0, 1]

Annotated Code

DSA Javascript

class TwoSum {
  static findTwoSum(nums, target) {
    const hash = {};
    for (let i = 0; i < nums.length; i++) {
      const complement = target - nums[i];
      if (hash[complement] !== undefined) {
        return [hash[complement], i];
      }
      hash[nums[i]] = i;
    }
    return [];
  }
}

// Driver code
const nums = [2, 7, 11, 15];
const target = 9;
const result = TwoSum.findTwoSum(nums, target);
console.log(`Indices: [${result[0]}, ${result[1]}]`);

const complement = target - nums[i];

Calculate the number needed to reach target with current number

if (hash[complement] !== undefined) {

Check if needed number was seen before

return [hash[complement], i];

Return indices of the two numbers that sum to target

hash[nums[i]] = i;

Store current number and its index for future checks

Output

Indices: [0, 1]

Complexity Analysis

Time: O(n) because we scan the list once and do constant time lookups in the hash

Space: O(n) because we store seen numbers in a hash map

vs Alternative: Compared to checking all pairs (O(n^2)), this is much faster using extra space

Edge Cases

Empty array

Returns empty array since no pairs exist

DSA Javascript

return [];

No two numbers sum to target

Returns empty array after full scan

DSA Javascript

return [];

Two numbers are the same and sum to target

Works correctly if both numbers appear at different indices

DSA Javascript

hash[nums[i]] = i;

When to Use This Pattern

When asked to find two elements that sum to a target quickly, use a hash map to remember seen numbers and check complements in one pass.

Common Mistakes

Mistake: Checking if complement exists after adding current number to hash
Fix: Check complement before adding current number to avoid using the same element twice

Mistake: Using hash.hasOwnProperty instead of direct undefined check causing false negatives
Fix: Use 'hash[complement] !== undefined' to correctly detect presence

Summary

Find two indices in an array whose values add up to a target using a hash map.

Use when you need a fast solution to find pairs summing to a target in one pass.

Remember to check for the complement before storing the current number to avoid duplicates.

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