Two Sum

Easy#1find a pair

You get an array of numbers and a target sum. Find two different elements that add up to the target and return their indices. There is exactly one such pair. Our example: [5, 1, 8, 6, 5, 3] with the sum 10 — the answer is [0, 4], the two fives.

1 Two SumWalkthrough · 1×

Example: [5, 1, 8, 6, 5, 3], sum 10. Below the array is the map: number and the index it stands at.

051128364553seennumber: index—
not reached yetin the mapcurrent numberits partnerthe answer

Start with an empty map: no number seen yet

01/21
restart · back · play · step
Speed
1function twoSum(nums, target):
2 seen = empty map
3 for i from 0 to len(nums) - 1:
4 need = target - nums[i]
5 if need in seen:
6 return [seen[need], i]
7 seen[nums[i]] = i
state
seen
{}
i
–
need
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Each number knows its partner in advance: the target minus the number. The only question is whether we have met it already, and the map answers that at once.
  2. Look up first, store after. Otherwise the first 5 would find itself in the map and return [0, 0].
  3. If the pair is at j < i, then by the time we reach i the number at j is in the map. So the pair is never missed, and one pass is enough.

Complexity

Time O(n): one pass, and a lookup or a store in the map takes O(1) on average. Memory O(n): the map may hold every number.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.