0
Challenge · 29Array & String Patterns
Seen-sets and complements
Patternsused in ~100% of apps
The move that closes the tier. Instead of searching forward for a partner you have not met yet, you remember everything you have already passed, and then the partner search becomes a single lookup.
Core idea. Walk forward once. At each item, work out exactly what partner it would need, and ask whether you have already seen that partner. Then record the current item. Searching becomes remembering, and a nested loop becomes one pass.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
Playground, this isn't a screenshot
nums = [2, 7, 11, 15], target 18
2needs16seen {}16 not seen. Write down 2
7needs11seen {2:0}11 not seen. Write down 7
11needs7seen {2:0, 7:1}7 was seen at index 1 → answer
Three lookups, no inner loop, and the original positions survive, which is exactly what sorting would have destroyed.
↑ play a little first, then dig in