Core pattern

Hashing: the coat check counter

Learn the hashing pattern through one picture you won’t forget, worked on Two Sum.

The example problem

Given a list of numbers and a target, find the positions of two numbers that add up to the target. Exactly one such pair exists.

Input:  nums = [3, 8, 5, 9, 4], target = 17
Output: [1, 3]   (8 + 9 = 17)

Picture it

Think of a coat-check counter. Each arriving guest carries a number. Before hanging their coat, the attendant asks: “is there already a coat here whose number is exactly what this guest needs to reach the target?” If yes, those two guests are the pair. If not, the coat goes on the rack. The rack is a dictionary that maps number → position, so the check takes one glance instead of searching every coat.

The key idea

For each number x, the partner you need is target − x. Store what you have seen in a dictionary and look the partner up in O(1).

Python

def two_sum(nums, target):
    seen = {}  # coat rack: number -> ticket
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i
    return []

Practise hashing

NeetCode 150 problems that use it

Arrays & Hashing ·