Counting and remembering with dicts and sets, turning O(n²) into O(n).
Key ideas
- A
setanswers "have I seen this?" in O(1). - A
dictis for counting and for going from a value to its index. - When you see two nested loops, ask whether a dict can replace the inner one.
Pattern
count = {}
for v in values:
count[v] = count.get(v, 0) + 1Finish these first:Arrays
Lessons
Each lesson explains one idea from zero and ends with a few tasks. Lessons open in order; the explanation can be read at any time.
Boss
06
Longest Streak
Function
The boss opens when every lesson of the topic is finished. Solve it too and the topic is complete, and the topics after it open.