Optimize the code · Easy

Speed Up Two Sum

Easy Make it fast Most askedSeen at Amazon, Google, Meta, Microsoft

twoSum(nums, target) returns the indices [i, j] (with i < j) of the two numbers that add up to target. Exactly one pair exists.

The brute-force version below is correct but compares every pair. On the 60,000-element case it misses the time budget. Make it run in one pass without changing the answers.

Example 1

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]

Example 2

Input: nums = [3, 2, 4], target = 6
Output: [1, 2]

The slow code

Every case must finish within 300 ms (budgets are per language in the editor).

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

function twoSum(nums: number[], target: number): number[] {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
  return [];
}

def two_sum(nums: list[int], target: int) -> list[int]:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

<?php

function twoSum(array $nums, int $target): array
{
    $n = count($nums);
    for ($i = 0; $i < $n; $i++) {
        for ($j = $i + 1; $j < $n; $j++) {
            if ($nums[$i] + $nums[$j] === $target) {
                return [$i, $j];
            }
        }
    }
    return [];
}

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) return new int[]{i, j};
            }
        }
        return new int[0];
    }
}

Hints

Hint 1

For each nums[j], which value would complete the pair?

Hint 2

Store the values you have already passed in a hash map from value to index.

Make it faster

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(n)

Why it is slow: two nested loops try every pair: n(n-1)/2 checks, about 1.8 billion for 60,000 numbers when the pair is at the end.

The fix: walk the array once and keep a map from each value seen so far to its index. For nums[j], the partner is target - nums[j]; if it is in the map, return [map[partner], j], otherwise store nums[j]. Checking before inserting is what stops an element from pairing with itself.

Optimized solution

function twoSum(nums, target) {
  const seen = new Map(); // value -> index
  for (let j = 0; j < nums.length; j++) {
    const i = seen.get(target - nums[j]);
    if (i !== undefined) return [i, j];
    seen.set(nums[j], j);
  }
  return [];
}

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>(); // value -> index
  for (let j = 0; j < nums.length; j++) {
    const i = seen.get(target - nums[j]);
    if (i !== undefined) return [i, j];
    seen.set(nums[j], j);
  }
  return [];
}

def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}  # value -> index
    for j, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], j]
        seen[x] = j
    return []

<?php

function twoSum(array $nums, int $target): array
{
    $seen = []; // value => index
    foreach ($nums as $j => $x) {
        if (isset($seen[$target - $x])) {
            return [$seen[$target - $x], $j];
        }
        $seen[$x] = $j;
    }
    return [];
}

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>(); // value -> index
        for (int j = 0; j < nums.length; j++) {
            Integer i = seen.get(target - nums[j]);
            if (i != null) return new int[]{i, j};
            seen.put(nums[j], j);
        }
        return new int[0];
    }
}

Common mistakes

Inserting the current value before looking up its partner: [3, 3] style inputs then return [0, 0].
Sorting to use two pointers loses the original indices unless you sort index pairs.

Follow-up questions

The array is already sorted: can you do it in O(1) extra space?
Return all pairs, not just one.

Speed Up Contains Duplicate · Easy
Speed Up Recursive Fibonacci · Easy
Speed Up the Most Frequent Word · Easy
Speed Up the Active-Customer Join · Easy
Speed Up Range Sum Queries · Medium
Speed Up Longest Consecutive Sequence · Medium