Two Sum

Approach Summary

Store complement (target - num) in map as you iterate. If current num is already in map, you found the pair.

Full Solution & Approach

Naively, for each element you scan the rest of the array for its complement — O(n²). Instead, trade space for time with a single pass and a hash map. As you iterate, the map stores each previously seen number as a key and its index as the value. For the current number n, compute target - n; if that complement is already in the map, the two indices are [stored_index, current_index] and you return immediately. Otherwise record n → i and continue. The algorithm relies on the guarantee that exactly one solution exists, so the first complement found is also the only valid answer. A hash map gives O(1) average lookup and insert, so the whole pass is O(n). Return the earlier index first, which the problem's output format expects.

One pass over the array with O(1) hash-map operations per element — O(n) time. The map holds at most n entries — O(n) space.

Solution Code

Solution

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen:
            return [seen[complement], i]
        seen[n] = i
    return []

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

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (seen.containsKey(complement)) return new int[]{seen.get(complement), i};
        seen.put(nums[i], i);
    }
    return new int[]{};
}

vector<int> twoSum(const vector<int>& nums, int target) {
    unordered_map<int,int> seen;
    for (int i = 0; i < (int)nums.size(); i++) {
        int complement = target - nums[i];
        if (seen.count(complement)) return {seen[complement], i};
        seen[nums[i]] = i;
    }
    return {};
}

Edge Cases to Watch

The pair may be the first and last elements
Negative numbers and zero are handled naturally by the arithmetic
Duplicate values — the map stores the latest index, but because we check before storing, an earlier duplicate is already present
Exactly one solution is guaranteed — no fallback needed

How to Recognize This Pattern

Find pair summing to target
Return indices

Complexity Analysis

Time Complexity

O(n)

Space Complexity