Remember what you have seen

Dictionaries and sets look things up in O(1) on average, so many problems become fast when you remember what you have already seen. Count things with a dict or Counter. Group things with a dict of lists (defaultdict(list) saves the setup). Find two numbers that add up to a target in a single pass by storing each number as you go.

How it reads

• Counter counts every item in one pass
• defaultdict(list) creates an empty list the first time a key is used
• two_sum asks "have I already seen the number I need?" instead of checking every pair

Cloud tip: Trading memory for speed is the most common algorithm trick there is: store what you learn, never recompute it.