Two Sum Problem Classic Hash Solution in DSA Typescript

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 price that matches the leftover gift card amount, you found your pair.

nums: [2] -> [7] -> [11] -> [15]
hash: {}
           ↑ current index

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 number 2 at index 0, look for 9 - 2 = 7 in hash

nums: [2, 7, 11, 15]
hash: {}
current index: 0

Why: We want to see if the pair for 2 is already found

Step 2: 7 not found in hash, add 2 with index 0 to hash

nums: [2, 7, 11, 15]
hash: {2: 0}
current index: 1

Why: Remember 2 for future pairs

Step 3: Check number 7 at index 1, look for 9 - 7 = 2 in hash

nums: [2, 7, 11, 15]
hash: {2: 0}
current index: 1

Why: See if 2 was seen before to form the pair

Step 4: 2 found in hash at index 0, return indices [0, 1]

nums: [2, 7, 11, 15]
hash: {2: 0}
result: [0, 1]

Why: Found the two numbers that add to target

Result:

nums: [2, 7, 11, 15]
result indices: [0, 1]

Annotated Code

DSA Typescript

class TwoSum {
  static findTwoSum(nums: number[], target: number): number[] {
    const hash: Record<number, number> = {};
    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(result.join(', '));

const complement = target - nums[i];

Calculate the number needed to reach target with current number

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

Check if complement was seen before

return [hash[complement], i];

Return indices of the two numbers that add to target

hash[nums[i]] = i;

Store current number and its index for future lookup

Output

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 up to n numbers in the hash

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

Edge Cases

Empty array

Returns empty array since no pairs exist

DSA Typescript

return [];

No two numbers add to target

Returns empty array after full scan

DSA Typescript

return [];

Two identical numbers add to target

Works correctly if both numbers appear and are stored separately

DSA Typescript

hash[nums[i]] = i;

When to Use This Pattern

When asked to find two elements summing to a target quickly, use a hash map to remember seen numbers for O(n) time.

Common Mistakes

Mistake: Checking if complement exists after adding current number to hash
Fix: Check for complement before adding current number to hash 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 of numbers that add up to a target using a hash map.

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

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 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