0
Challenge · 39Structures You Build Yourself
Fast and slow pointers
Structuresused in ~85% of apps
Two walkers on the same track, one moving twice as fast. If the track is a loop they will meet, if it ends, the fast one gets there first. That one idea answers a whole family of questions with no extra memory at all.
Core idea. Move one pointer one step at a time and another two steps at a time. The gap between them changes by exactly one per move, and that single fact is enough to detect a cycle, find the middle, or locate the nth item from the end, in one pass, with two variables.
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
1 → 2 → 3 → 4 → 5 → back to 3
1
S F2
3
4
5
1
2
S3
F4
5
1
2
3
S4
5
F1
2
3
4
S F5
The gap shrinks by exactly one per move. A gap that always shrinks by one must reach zero, which is why meeting is guaranteed, not likely.
↑ play a little first, then dig in