Coding problem · Easy · Arrays & Hashing

Two Sum

Easy Algorithms & data structures Most askedSeen at Google, Amazon, Meta, Microsoft

Given an array of integers nums and an integer target, return the 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. Return the indices in ascending order.

Example 1

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

Example 2

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

Constraints

2 <= nums.length <= 10^4
Exactly one valid answer exists

Hints

Hint 1

A brute-force double loop is O(n²). What would let you check 'have I seen target − x?' in O(1)?

Hint 2

Store each value's index in a hash map as you scan; look up the complement before inserting.

Write and run your solution

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

Solution and explanation

Show the solution

Time O(n) · Space O(n)

Scan once, remembering where each value appeared. For each x, the partner we need is target - x; if it's already in the map we have the answer. Checking before inserting prevents using the same element twice.

Reference solution

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

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

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

<?php

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

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

Common mistakes

Inserting x before checking — [3,3] with target 6 then returns the same index twice.
Sorting the array first loses the original indices.

Follow-up questions

What if the array is sorted? (two pointers, O(1) space)
What if you must return all pairs?