Two Sum

easy

arrayhash-tableAsked at new-york-times

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

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

Output: [0,1]

nums[0] + nums[1] = 2 + 7 = 9.

Constraints

2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
Exactly one valid answer exists.

Intuition

The most direct approach checks every pair of numbers: for each index i, walk every later index j and test whether nums[i] + nums[j] equals target. The first matching pair is the answer, and because j always starts after i the two indices come out in ascending order for free.

function twoSum(nums, target) {
  // Try every distinct pair (i, j) with i < j.
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      // First pair that hits target wins; i < j keeps indices ascending.
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
  return []; // problem guarantees a solution, so this is unreachable
}

Brute force — test every pair: O(n²).

This is O(n²) — for each element we rescan the whole rest of the array. Can we do better?

The inner loop is really asking one narrow question: have I already seen the number that completes this pair? For a value x, that partner is exactly target − x — there is only one number that works. So instead of scanning for it, we can remember every value we've passed in a hash map keyed by value, and look the partner up in O(1).

Storing value → index lets that lookup also hand back where the partner was, which is what we need to return. This is the core hash maps trick: trade O(n) space for O(1) membership-and-recall, collapsing the nested scan into a single pass.

One pass suffices if we check before we insert: at index i we ask whether target − nums[i] is already stored, and only then add nums[i] ourselves. Checking first means we never pair an element with itself, and the stored partner is always at an earlier index — so [seen, i] is already ascending.

Walking it through:

nums = [3, 8, 2, 7, 5], target = 9 — one-pass seen-map

i↓

need 9 − 3 = 6 → not seen, store 3 → seen = {3:0}

Partner of 3 is 6; nothing stored yet, so record value 3 at index 0.

i↓

need 9 − 8 = 1 → not seen, store 8 → seen = {3:0, 8:1}

A miss: 1 was never seen. Add value 8 at index 1 and move on.

i↓

need 9 − 2 = 7 → not seen, store 2 → seen = {3:0, 8:1, 2:2}

Still no partner — 7 hasn't appeared. Record value 2 at index 2.

i↓

need 9 − 7 = 2 → seen at index 2 → return [2, 3]

Hit: the partner 2 was stored back at index 2. The pair is [2, 3], already ascending.

Optimization

Brute force

Check every pair (i, j) with i < j and return the first whose values sum to target. Iterating i < j keeps the indices ascending for free.

O(n²) time, O(1) space — simple, but quadratic on large inputs.

function twoSum(nums, target) {
  // Try every distinct pair (i, j) with i < j.
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      // First pair that hits target wins; i < j keeps the indices ascending.
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
  return []; // guaranteed solution means this is unreachable
}

Hash map (one pass)

Walk the array once, keeping a map of value → index seen so far. For each nums[i], the partner you need is target - nums[i]; if it's already in the map you've found the pair. The stored index is earlier, so [seen, i] is ascending.

O(n) time, O(n) space.

function twoSum(nums, target) {
  // Map each value we've passed to the index it lives at.
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    // The one number that completes this pair.
    const need = target - nums[i];
    // Check before inserting: never pairs an element with itself, and
    // the stored partner is at an earlier index, so [seen, i] is ascending.
    if (seen.has(need)) return [seen.get(need), i];
    // Partner not seen yet — record this value so a later element can find it.
    seen.set(nums[i], i);
  }
  return []; // guaranteed solution means this is unreachable
}

Complexity analysis

Time complexity: O(n). Here's why:

The array is scanned once, left to right, visiting each element a single time.
Per element the work is O(1): one hash-map lookup for the partner and at most one insertion.

There is no nested loop — the inner scan of the brute force is replaced by a constant-time map probe — so the whole pass is O(n), where n is the length of nums.

Space complexity: O(n). Here's why:

The seen map can hold up to one entry per element if the answer is the final pair.
Each entry is a value → index mapping taking O(1), so the map grows linearly with the input.

That extra map is the cost of the speed-up — we spend O(n) space to drop the time from O(n²) to O(n). The returned two-index array isn't counted as auxiliary space.

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
nums = [1,4], target = 5	[0,1]	Smallest valid input — two elements that sum to target.
nums = [1,2,4], target = 8	[]	No pair sums to target — the unreachable fallback returns [].
nums = [-4,-1,-3,-8], target = -7	[0,2]	Negatives — −4 + −3 = −7, found by a later index.
nums = [5,5,3], target = 10	[0,1]	Duplicate values — two equal 5s pair up; second is the partner.
nums = [6,2,8,1,5], target = 6	[3,4]	Target reached only by a later pair: 1 + 5 at the end.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor