Two Sum

EasyGoogleAmazonMetaAppleMicrosoft

Problem

Given an array of integers nums and an integer target, return indices of the two numbers that add up to target. Each input has exactly one solution and you may not use the same element twice.

Intuition — the key insight

For every number x we encounter, we need to know if (target - x) has already been seen. A HashMap gives us O(1) lookup — so instead of checking every pair (O(n²)), we do a single pass storing each number's index, checking for its complement at every step.

Approach

1. Brute force (O(n²))

Check every pair (i, j) where i ≠ j. Return when nums[i] + nums[j] === target. Too slow for large inputs.

2. Optimal — single pass HashMap

Initialize an empty hashmap. For each index i, compute complement = target - nums[i]. If complement is already in the map, return [map[complement], i]. Otherwise, store nums[i] → i in the map and continue.

Complexity

Time

O(n)

Space

O(n)

We iterate through the array once — O(n). The hashmap stores at most n elements — O(n) space. Each lookup and insert is O(1) average.

Solution code

Python

def twoSum(self, nums: List[int], target: int) -> List[int]:
    seen = {}  # value -> index
    
    for i, num in enumerate(nums):
        complement = target - num
        
        if complement in seen:
            return [seen[complement], i]
        
        seen[num] = i
    
    return []  # guaranteed to have solution

Edge cases to remember

⚠Same element used twice: store AFTER checking — this prevents using nums[i] as its own complement

⚠Negative numbers: complement can be negative, hashmap handles this fine

⚠Duplicate values: the map stores the most recent index, but since there's exactly one solution this is fine

Hints

What pattern do you think this problem uses?