Data structures problem 2 of 30

Two sum

Data structures
Easy

Given a list of integers nums and an integer target, return the indices of the two numbers that add up to target. Exactly one answer exists, and you may not use the same element twice.

Can you beat O(n²)?

two_sum([2, 7, 11, 15], 9)
# [0, 1]

Show hint

As you walk the list, remember every number you have already seen and where. For each new number, what partner are you looking for?

Show solution

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

A dictionary gives O(1) lookups, so one pass is enough: O(n) time and O(n) extra space. Checking before inserting stops a number from pairing with itself.

Want a problem like this every day? See today's problem and keep a streak going.