Two Sum Problem Classic Hash Solution in DSA Typescript - 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 Classic Hash Solution?

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

beginner

What is the time complexity of the Two Sum Problem Classic Hash Solution?

O(n), where n is the number of elements in the array, because each element is processed once and hash map lookups are O(1).

beginner

In the Two Sum Problem Classic Hash Solution, what happens if no two numbers add up to the target?

The function returns an empty array or a special value indicating no solution was found.

beginner

Explain the role of the complement in the Two Sum Problem Classic 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.

What data structure is primarily used in the Two Sum Problem Classic Hash Solution?

A Hash map (object)

B Array

C Linked list

D Stack

The solution uses a hash map to store numbers and their indices for quick lookup.

What is the time complexity of the Two Sum Problem Classic Hash Solution?

A O(n^2)

B O(n log n)

C O(n)

D O(log n)

Each element is processed once and hash map lookups are O(1), so total time is O(n).

What do you check for each number while iterating in the Two Sum Problem Classic Hash Solution?

A If the number itself is in the hash map

B If the number is greater than the target

C If the number is even

D If the complement (target - number) is in the hash map

We check if the complement exists in the hash map to find the pair that sums to the target.

What does the Two Sum Problem Classic Hash Solution return when a valid pair is found?

A The indices of the two numbers

B The sum of the two numbers

C The two numbers themselves

D The target value

The solution returns the indices of the two numbers that add up to the target.

What happens if no two numbers add up to the target in the Two Sum Problem Classic Hash Solution?

A Returns the first number

B Returns an empty array or no result

C Throws an error

D Returns the target

If no pair is found, the function returns an empty array or a special value indicating no solution.

Describe step-by-step how the Two Sum Problem Classic Hash Solution finds the indices of two numbers that add up to a target.

Think about how the hash map helps find the pair quickly.

Explain why using a hash map improves the efficiency of solving the Two Sum Problem compared to a brute force approach.

Focus on how many times each element is processed.

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