Warm-up tutorial

Warm-up. Before the first stage, one idea: Big O, how the work grows as the input grows.

Comparing every pair is O of n squared. Ten items make forty-five pairs. A hundred thousand make about five billion. One pass is a blink; all those pairs take minutes.

So open the toolbox. Its first tool is a hash map, a wall of lockers. Ask if a value is inside, and it answers in one hop: O of one, on average.

The clue in a problem: if you're comparing every pair, ask what you could remember instead.

One pass that remembers each item in the map turns O of n squared into O of n. Now let's use it on Two Sum.