Two Sum

Easy

Find two numbers in an array that add up to a target value.

Time: O(n)•Space: O(n)

Problem Statement

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Example:

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] == 9, so we return [0, 1]

Note: You may assume that each input has exactly one solution, and you may not use the same element twice.

Approach

The optimal solution uses a hash map to achieve O(n) time complexity:

  1. Create an empty hash map to store numbers and their indices
  2. Iterate through the array once
  3. For each number, calculate its complement (target - current number)
  4. Check if the complement exists in the hash map
  5. If yes, return the indices. If no, add the current number to the map

Why this works: By storing each number as we iterate, we can check in O(1) time if the complement has been seen before, avoiding nested loops.

Solution

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 null;
}

Interactive Visualizer

See the algorithm in action step-by-step:

i=0
2
i=1
7
i=2
11
i=3
15
Hash Map
Empty
Step 1 / 0Infinity%

Time & Space Complexity

Time Complexity
O(n)

Single pass through the array

Space Complexity
O(n)

Hash map storage for n elements

Discussion

Have questions or want to discuss alternative approaches? Join the conversation below.

Back to DSA Visualizer