Two Sum Problem Classic Hash Solution in DSA Typescript - Deep Dive

Overview - Two Sum Problem Classic Hash Solution

What is it?

The Two Sum problem asks us to find two numbers in a list that add up to a specific target number. We want to return the positions of these two numbers. The classic hash solution uses a fast way to remember numbers we've seen so far to find the answer quickly. This helps us avoid checking every pair one by one.

Why it matters

Without this solution, finding two numbers that add up to a target would take a long time, especially for big lists. This slow method wastes time and computer power. The hash solution makes it fast and efficient, which is important in apps like shopping carts, games, or any place where quick matching is needed.

Where it fits

Before this, you should understand arrays (lists) and basic loops. After this, you can learn about more complex searching and sorting algorithms, or how to solve similar problems using trees or graphs.

Mental Model

Core Idea

Remember numbers you've seen so far to quickly find if the matching number for the target exists.

Think of it like...

It's like checking your pockets for a coin that pairs with the one you just found to make a dollar, instead of searching the whole room every time.

Input Array: [2, 7, 11, 15]
Target: 9

Step-by-step:

Index: 0, Number: 2
Hash Map: {}
Check if 9 - 2 = 7 is in Hash Map? No
Add 2 to Hash Map with index 0

Index: 1, Number: 7
Hash Map: {2:0}
Check if 9 - 7 = 2 is in Hash Map? Yes, at index 0
Return [0,1]

Build-Up - 7 Steps

1

Foundation

Understanding the Two Sum Problem

Concept: Learn what the problem asks: find two numbers that add up to a target and return their positions.

Given an array of numbers and a target number, we want to find two different numbers in the array that add up exactly to the target. For example, if the array is [2, 7, 11, 15] and the target is 9, the answer is the positions of 2 and 7 because 2 + 7 = 9.

Result

Clear understanding of the problem and what output is expected.

Knowing exactly what the problem wants helps avoid confusion and guides how to approach the solution.

2

Foundation

Brute Force Approach Basics

Concept: Try every pair of numbers to see if they add up to the target.

We can check each number with every other number to see if their sum equals the target. This means two loops: the first picks a number, the second checks all others. For example, check 2 + 7, then 2 + 11, then 7 + 11, and so on.

Result

We find the correct pair but with many checks, which is slow for big lists.

Understanding the slow method shows why we need a faster way.

3

Intermediate

Introducing Hash Map for Fast Lookup

Concept: Use a hash map (dictionary) to remember numbers and their positions for quick searching.

Instead of checking all pairs, we keep a map of numbers we've seen and their indexes. For each number, we check if the number needed to reach the target is already in the map. If yes, we found our pair. If no, we add the current number to the map and continue.

Result

We find the pair in one pass through the list, making it much faster.

Using a hash map turns a slow double loop into a fast single loop by trading space for speed.

4

Intermediate

Implementing the Hash Solution in TypeScript

🤔Before reading on: do you think we check the map before or after adding the current number? Commit to your answer.

Concept: Write the code that uses a hash map to solve the problem efficiently.

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 []; } // Example: // Input: nums = [2,7,11,15], target = 9 // Output: [0,1]

Result

The function returns the indexes of the two numbers that add up to the target quickly.

Checking the map before adding the current number avoids using the same element twice and ensures correctness.

5

Intermediate

Handling Edge Cases and No Solution

🤔Before reading on: What should the function return if no two numbers add up to the target? Commit to your answer.

Concept: Decide what to do if no pair is found and handle special cases like empty arrays or single-element arrays.

If no pair is found, the function returns an empty array []. For empty or single-element arrays, no pair exists, so the function also returns []. This prevents errors and makes the function robust.

Result

The function safely handles all inputs without crashing or wrong answers.

Thinking about edge cases prevents bugs and makes your code reliable in real-world use.

6

Advanced

Time and Space Complexity Analysis

🤔Before reading on: Do you think the hash solution uses more or less memory than the brute force? Commit to your answer.

Concept: Understand how fast and memory-heavy the hash solution is compared to other methods.

The hash solution runs in O(n) time because it goes through the list once. It uses O(n) extra space for the hash map to store numbers. The brute force takes O(n^2) time but uses O(1) space. This tradeoff is usually worth it for speed.

Result

Clear understanding of why the hash solution is preferred for large inputs.

Knowing complexity helps choose the right solution for different situations.

7

Expert

Surprising Behavior with Duplicate Numbers

🤔Before reading on: If the array has duplicates, does the hash solution always find the first correct pair? Commit to your answer.

Concept: Explore how duplicates affect which pair is returned and why order matters.

If duplicates exist, the hash map stores the last index of a number. This means the solution may return the pair involving the last occurrence, not the first. For example, nums = [3,3], target = 6 returns [0,1]. But nums = [3,3,2], target = 5 returns [1,2] because the last 3 overwrites the first in the map.

Result

The solution is correct but may not always return the earliest pair in the list.

Understanding this helps when the problem requires the earliest pair or all pairs, guiding how to adjust the solution.

Under the Hood

The hash map stores each number as a key and its index as the value. When processing a number, the algorithm calculates the complement (target - current number) and checks if this complement exists in the map. If yes, it returns the stored index and current index. This works because hash maps provide constant time lookup on average, making the search efficient.

Why designed this way?

The hash solution was designed to reduce the time complexity from quadratic to linear by using extra memory. Alternatives like sorting and two pointers require sorted input and lose original indexes, so the hash map preserves order and index information. This design balances speed and simplicity.

┌───────────────┐
│ Start array   │
│ [2,7,11,15]   │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Initialize    │
│ empty hash map│
└──────┬────────┘
       │
       ▼
┌─────────────────────────────┐
│ For each number in array:    │
│ 1. Calculate complement      │
│ 2. Check if complement in map│
│   - If yes, return indexes   │
│   - If no, add number to map │
└─────────────┬───────────────┘
              │
              ▼
       ┌─────────────┐
       │ Return pair │
       └─────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does the hash solution check pairs in order of appearance? Commit yes or no.

Common Belief: The hash solution always returns the first pair found in the array order.

Reality: The hash solution returns the first pair it finds during iteration, which may not be the earliest pair if duplicates exist.

Why it matters: Assuming it returns the earliest pair can cause bugs if the problem requires the first pair by index order.

Quick: Is the hash map lookup always O(1) in practice? Commit yes or no.

Common Belief: Hash map lookups are always constant time, so the solution is always fast.

Reality: Hash map lookups are average O(1), but worst-case can degrade due to collisions, though rare with good hash functions.

Why it matters: Understanding this prevents overconfidence in performance and encourages considering input characteristics.

Quick: Can the hash solution work if the array is sorted? Commit yes or no.

Common Belief: The hash solution requires the array to be sorted to work correctly.

Reality: The hash solution works on unsorted arrays and does not require sorting.

Why it matters: Misunderstanding this can lead to unnecessary sorting, which wastes time and complicates the solution.

Quick: Does the hash solution use less memory than brute force? Commit yes or no.

Common Belief: The hash solution uses less memory than brute force because it is faster.

Reality: The hash solution uses extra memory to store the hash map, so it uses more memory than brute force.

Why it matters: Ignoring memory use can cause problems in memory-limited environments.

Expert Zone

1

The hash map stores the last occurrence of a number, which affects which pair is returned when duplicates exist.

2

The solution assumes numbers are hashable and that hash collisions are minimal for performance.

3

In some languages or environments, using a hash map may have overhead; alternative data structures might be preferred.

When NOT to use

Avoid this approach when memory is very limited or when you need all pairs, not just one. In sorted arrays, two-pointer technique is more memory efficient. For streaming data, other algorithms may be needed.

Production Patterns

Used in real-time systems for quick matching, such as fraud detection, recommendation engines, and gaming. Often combined with input validation and error handling for robustness.

Connections

Hash Tables

The Two Sum hash solution is a direct application of hash tables for fast lookup.

Understanding hash tables deeply improves grasp of why the Two Sum solution is efficient.

Sliding Window Technique

Both use linear scans and auxiliary data structures to solve problems efficiently.

Knowing sliding window helps understand how to optimize problems involving sequences and sums.

Inventory Management in Retail

Matching items to fulfill orders quickly is similar to finding pairs that sum to a target.

Seeing algorithm patterns in business processes helps appreciate their practical value.

Common Pitfalls

#1 Checking the hash map after adding the current number causes using the same element twice.

Wrong approach:

function twoSum(nums: number[], target: number): number[] {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
map.set(nums[i], i);
const complement = target - nums[i];
if (map.has(complement)) {
return [map.get(complement)!, i];
}
}
return [];
}

Correct approach:

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 [];
}

Root cause:

Misunderstanding the order of operations causes the algorithm to find the same element as its complement.

#2 Not handling the case when no pair exists leads to undefined or errors.

Wrong approach:

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);
}
// Missing return here
}

Correct approach:

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 [];
}

Root cause:

Forgetting to return a default value when no solution is found causes runtime errors.

#3 Using an array instead of a hash map for lookup causes slow performance.

Wrong approach:

function twoSum(nums: number[], target: number): number[] {
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];
}
}
}
return [];
}

Correct approach:

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 [];
}

Root cause:

Not using a hash map misses the opportunity to optimize time complexity.

Key Takeaways

The Two Sum problem asks for two numbers in a list that add up to a target and returns their positions.

The classic hash solution uses a map to remember numbers seen so far, enabling quick lookup of complements.

This approach reduces time complexity from O(n^2) to O(n) by trading extra memory for speed.

Order of operations matters: check the map before adding the current number to avoid using the same element twice.

Understanding edge cases and duplicates is important for correct and predictable results.

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