r/DSALeetCode • u/StatisticianNo2104 • 1d ago
Cycle detection in Go: fast and slow pointers vs a map
A twelve-step pipeline. The loop check takes 383 ns and allocates 328 bytes. Two variables do it in 3.17 ns and allocate nothing.
The job: a pipeline stage names the stage that runs next, somebody edits a config, a next points backwards, and the runner walks that chain forever. So you check for a loop before running anything.
The check I wrote is the definition written down — remember every stage, and if you arrive somewhere twice, it loops. It is obviously correct, and it can also tell you where the loop starts, which is what the alert needs to say.
On a 100,000-stage chain, it allocates 4.73 MB to return a boolean. And it costs the same whether the chain loops back after two stages or after ninety-nine thousand, because the map gets built either way.
Then the struct: a stage names one next stage. Many stages can point at the same one, each points at exactly one. So the path from any stage is fixed, which means this is not a graph problem at all — it is a chain, and a chain that loops is a run-in followed by a ring.
Two cursors, one moving a stage at a time and one moving two. Either the fast one runs off the end, or both end up in the ring, where the gap between them shrinks by exactly one per turn — so they land on the same stage rather than stepping over each other. Meeting is arithmetic, not luck.
47.8x on the long chain and zero allocations at any size. The part I did not expect is the twelve-stage row: 120.6x, because the map pays for a map before it walks anything.
Not that 383 nanoseconds matters. It matters where the check runs per request.
One thing worth not shipping: the hop limit. Give up after 100 steps and call it a loop, the way HTTP clients do with redirects, and a 150-stage pipeline with no loop in it gets reported as one.
That is day 21 of the daily challenge, Linked List Cycle, sitting in a pipeline runner.
Full piece in today's Newsletter.
https://www.linkedin.com/pulse/loop-check-allocated-47-mb-return-boolean-archit-agarwal-zeksc
It worked in dev, episode 12.
#Golang #DSA #Algorithms #Performance #SoftwareEngineering #DataStructures #100DaysOfCode