Two Sum Problem Classic Hash Solution in DSA Javascript - Time & Space Complexity

Time Complexity: Two Sum Problem Classic Hash Solution

O(n)

Understanding Time Complexity

We want to understand how fast the classic hash solution for the Two Sum problem runs as the input size grows.

Specifically, how does the number of steps change when the list of numbers gets bigger?

Scenario Under Consideration

Analyze the time complexity 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 [];
}
    

This code finds two numbers in the array that add up to the target using a hash map for quick lookups.

Identify Repeating Operations

• Primary operation: One loop that goes through each number once.
• How many times: Exactly once for each number in the input array.
• Inside the loop, checking and adding to the map are quick, constant-time operations.

How Execution Grows With Input

As the list gets bigger, the number of steps grows directly with the number of numbers.

Input Size (n)	Approx. Operations
10	About 10 checks and inserts
100	About 100 checks and inserts
1000	About 1000 checks and inserts

Pattern observation: The steps increase evenly as the input size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the two numbers grows in a straight line with the size of the input.

Common Mistake

[X] Wrong: "Because there is a loop inside a loop, the time is O(n²)."

[OK] Correct: There is only one loop here; the map lookups are very fast and do not add extra loops.

Interview Connect

Understanding this solution's time complexity helps you explain why using a hash map is efficient and preferred in interviews.

Self-Check

"What if we used a nested loop to check every pair instead of a hash map? How would the time complexity change?"

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