Two-sum with a hash map in Python

The classic interview problem in linear time.

def two_sum(numbers, target):
    seen = {}
    for i, n in enumerate(numbers):
        need = target - n
        if need in seen:
            return (seen[need], i)
        seen[n] = i
    return None


pair = two_sum([2, 7, 11, 15], 9)
miss = two_sum([1, 2, 3], 100)

How it works

1. A dict remembers each value's index as it scans.
2. For each number it looks up the needed complement.
3. A hit returns the pair; otherwise it records and moves on.

Keywords and builtins used here

• def
• enumerate
• for
• if
• return
• two_sum

The run, in numbers

Lines

12

Characters to type

220

Tokens

79

Three-star pace

100 tpm

At the three-star pace of 100 tokens a minute, this run takes about 47 seconds.

Type this snippet

Step 1 of 5 in Algorithms, step 51 of 72 in Language basics.

← Previous Next →