Two Sum Problem Classic Hash Solution in DSA Javascript - 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. This problem is common in coding interviews and helps us practice using data structures to find answers quickly. The classic hash solution uses a special storage called a hash map to find the answer in one pass through the list.

Why it matters

Without an efficient way to find pairs that add up to a target, we would have to check every possible pair, which takes a long time for big lists. The hash solution makes this fast and practical, saving time and computing power. This is important in real-world apps where speed matters, like searching for matching items or detecting pairs in data.

Where it fits

Before learning this, you should understand arrays (lists) and basic loops. After this, you can learn more about hash maps, sets, and other searching algorithms. This problem is a stepping stone to mastering efficient data lookup and problem-solving techniques.

Mental Model

Core Idea

Use a hash map to remember numbers seen so far so you can quickly check if the needed partner number exists to reach the target sum.

Think of it like...

Imagine you are shopping with a list of prices and a gift card with a fixed amount. As you look at each item, you check if you already saw another item that together with this one exactly uses up your gift card. You keep a mental note (hash map) of prices you've seen to quickly find the matching pair.

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

Step-by-step:
Index 0: 2 -> Need 7 (9 - 2)
Hash Map: {}
Add 2: {2:0}

Index 1: 7 -> Need 2 (9 - 7)
Hash Map: {2:0}
Found 2 at index 0

Result: Indices [0,1]

Build-Up - 6 Steps

1

Foundation

Understanding the Two Sum Problem

Concept: Learn what the Two Sum problem asks for and why it matters.

You have a list of numbers and a target number. Your job is to find two different numbers in the list that add up exactly to the target. You return their positions (indexes). For example, if the list is [1, 3, 5] and the target is 4, the answer is indexes [0,1] because 1 + 3 = 4.

Result

Clear understanding of the problem and what output is expected.

Knowing the problem goal clearly helps you focus on finding pairs that sum to the target, not just any numbers.

2

Foundation

Brute Force Approach Basics

Concept: Try every pair to find the sum, understanding the simplest but slow method.

Check every pair of numbers in the list by using two loops: one for the first number and one for the second. If their sum equals the target, return their indexes. This works but takes a lot of time for big lists because it checks all pairs.

Result

For list [2,7,11,15] and target 9, output is [0,1].

Seeing the brute force method shows why we need a faster way for large lists.

3

Intermediate

Introducing Hash Map for Fast Lookup

Concept: Use a hash map to store numbers and their indexes for quick searching.

Instead of checking all pairs, keep a hash map (an object in JavaScript) that remembers numbers you've seen and their positions. For each number, calculate the needed partner (target - current number). Check if this partner is already in the hash map. If yes, return both indexes. If no, add the current number to the map and continue.

Result

For [2,7,11,15] and target 9, the hash map helps find [0,1] quickly.

Using a hash map reduces the search time from checking all pairs to just one pass through the list.

4

Intermediate

Implementing the Classic Hash Solution in JavaScript

🤔Before reading on: do you think the solution needs one or two passes through the array? Commit to your answer.

Concept: Write code that uses one pass and a hash map to solve Two Sum efficiently.

function twoSum(nums, target) { const map = {}; for (let i = 0; i < nums.length; i++) { const complement = target - nums[i]; if (map.hasOwnProperty(complement)) { return [map[complement], i]; } map[nums[i]] = i; } return []; } Example: Input: nums = [2,7,11,15], target = 9 Output: [0,1]

Result

[0,1]

Knowing that one pass with a hash map is enough makes the solution both elegant and efficient.

5

Advanced

Handling Edge Cases and Duplicate Numbers

🤔Before reading on: do you think the hash map solution works correctly if the list has duplicate numbers? Commit to yes or no.

Concept: Understand how the solution behaves with duplicates and what to watch out for.

If the list has duplicates, the hash map stores the last index of each number. This works because we check for the complement before adding the current number. For example, nums = [3,3], target = 6 returns [0,1]. But if the target is twice a number, ensure you don't use the same element twice by checking indexes carefully.

Result

Correct pairs found even with duplicates, e.g., [3,3] with target 6 returns [0,1].

Understanding the order of checking and adding to the map prevents bugs with duplicates.

6

Expert

Why Hash Map Lookup is O(1) and Its Impact

🤔Before reading on: do you think hash map lookups always take constant time? Commit to yes or no.

Concept: Explore the internal behavior of hash maps and their average constant time lookup.

Hash maps use a technique called hashing to convert keys into indexes in an internal array. This lets them find values quickly, usually in constant time (O(1)). However, in rare cases like many collisions, lookup can slow down. Still, for Two Sum, this means the solution is very fast compared to checking all pairs.

Result

The solution runs in linear time O(n), much faster than quadratic O(n²).

Knowing why hash maps are fast helps you trust and choose this approach for performance-critical problems.

Under the Hood

The hash map stores each number as a key and its index as the value. When processing each number, the algorithm calculates the complement (target - current number) and checks if this complement exists in the hash map. This check is very fast because hash maps use a hashing function to jump directly to the stored value's location. If found, the pair is returned immediately. Otherwise, the current number is added to the map for future checks.

Why designed this way?

This approach was designed to reduce the time complexity from O(n²) to O(n) by trading space for speed. Instead of checking every pair, it remembers what it has seen to avoid repeated work. Alternatives like sorting and two pointers require sorted input and extra steps, while the hash map works directly on unsorted data.

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

Processing:

[Start]
  i=0, num=2
  complement=7
  map: {}
  Add 2: map={2:0}

[Next]
  i=1, num=7
  complement=2
  map: {2:0}
  Found complement 2 at index 0
  Return [0,1]

Myth Busters - 3 Common Misconceptions

Quick: Does the hash map solution check pairs in order or randomly? Commit to your answer.

Common Belief: People often think the hash map solution checks pairs randomly or out of order.

Reality: The solution processes numbers in order, checking for complements before adding the current number to the map, ensuring pairs are found in the order they appear.

Why it matters: Misunderstanding order can lead to confusion about which pair is returned first or bugs when duplicates exist.

Quick: Do you think the hash map solution can find pairs if the target is twice a number? Commit yes or no.

Common Belief: Some believe the solution fails if the target is twice a number, like target=6 and number=3 twice.

Reality: The solution works correctly because it checks for the complement before adding the current number, allowing pairs of the same number at different indexes.

Why it matters: Believing this false limitation might cause unnecessary complex code or wrong solutions.

Quick: Is the hash map lookup always guaranteed to be constant time? Commit yes or no.

Common Belief: Many think hash map lookups are always O(1) with no exceptions.

Reality: While average lookup is O(1), worst-case can degrade due to collisions, but this is rare and usually negligible in practice.

Why it matters: Understanding this prevents overconfidence and helps in choosing data structures wisely for critical systems.

Expert Zone

1

The order of checking complement before inserting current number avoids using the same element twice and handles duplicates elegantly.

2

Hash maps in JavaScript are objects, but using Map() can avoid issues with keys like '__proto__' and improve clarity.

3

In very large datasets, memory usage of the hash map can be a bottleneck, so sometimes sorting and two-pointer methods are preferred.

When NOT to use

Avoid the hash map solution when memory is very limited or when the input is already sorted and you want to save space. In such cases, the two-pointer technique after sorting is better. Also, if you need all pairs instead of just one, this method needs modification or a different approach.

Production Patterns

In real systems, this pattern is used in fraud detection (finding pairs of transactions), recommendation engines (matching pairs of items), and real-time analytics where quick pair matching is needed. The hash map approach is often combined with streaming data techniques for continuous input.

Connections

Hash Map Data Structure

Builds-on

Understanding the Two Sum problem deeply reinforces how hash maps enable fast lookups, a core skill for many algorithms.

Sorting and Two-Pointer Technique

Alternative approach

Knowing Two Sum's hash solution helps appreciate when sorting and two-pointer methods are better, especially for space efficiency.

Real-Time Fraud Detection Systems

Application domain

The pattern of quickly finding pairs that meet a condition is fundamental in fraud detection, showing how algorithmic thinking applies beyond coding.

Common Pitfalls

#1 Using the hash map after adding the current number, causing the same element to be matched with itself.

Wrong approach:

function twoSum(nums, target) {
const map = {};
for (let i = 0; i < nums.length; i++) {
map[nums[i]] = i;
const complement = target - nums[i];
if (map.hasOwnProperty(complement)) {
return [map[complement], i];
}
}
return [];
}

Correct approach:

function twoSum(nums, target) {
const map = {};
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.hasOwnProperty(complement)) {
return [map[complement], i];
}
map[nums[i]] = i;
}
return [];
}

Root cause:

Adding the current number before checking complement allows matching the number with itself, which is invalid.

#2 Using an array method like indexOf inside the loop, causing O(n²) time complexity.

Wrong approach:

function twoSum(nums, target) {
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
const j = nums.indexOf(complement);
if (j !== -1 && j !== i) {
return [i, j];
}
}
return [];
}

Correct approach:

function twoSum(nums, target) {
const map = {};
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.hasOwnProperty(complement)) {
return [map[complement], i];
}
map[nums[i]] = i;
}
return [];
}

Root cause:

Using indexOf inside a loop causes repeated scanning, making the solution slow for large inputs.

Key Takeaways

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

A brute force approach checks all pairs but is slow; the hash map solution finds the pair in one pass efficiently.

Using a hash map lets you quickly check if the needed partner number exists, reducing time from quadratic to linear.

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

Understanding hash map behavior and edge cases like duplicates ensures robust and fast solutions.

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