Two Sum

Lesson 3.2 · Easy · Look up a partner · 6 min · by Vinay C

We'll cover the following

Overview
Watch it run
The idea
Complexity
In Python
Summary

In an unsorted array, find two numbers that add up to the target.

Watch it run

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

i410

441

372

333

504

315

486

257

128

309

4010

4311

1012

2813

2414

2715

Looking at 41. It needs a partner of -2. Have we seen -2?

seen {}

1 / 32

The idea

Complexity

Time	Space	Why
`O(n)`	`O(n)`	One pass with O(1) average lookups; the map can hold every value.

In Python

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

</> Now code it →Try it on LeetCode: Two Sum →

Summary: say it in the interview

For each number, ask whether its partner has already appeared. A map answers that in one step, so one pass is enough instead of two nested loops.
Time O(n), space O(n). One pass with O(1) average lookups; the map can hold every value.