Cycle Detection
What is this?
Some processes step from one state to the next in a fixed, repeatable way. If such a process ever lands on a state it has visited before, it is stuck in a loop and will repeat forever. The trick here is to remember every state you have seen in a hash set, so the moment one shows up twice you have caught the loop — just like noticing you have walked past the same shop twice and realizing you are going in circles.
💡 Fun fact: There is a clever alternative that needs almost no memory — Floyd's "tortoise and hare", where one pointer moves twice as fast as the other and they are guaranteed to collide inside any loop. Robert Floyd, who won the Turing Award, is credited with it, though he never published the algorithm himself.
🔓 The 1 problem in this chapter is free. Sign in with Google or Microsoft to start solving.
Core idea: When a process moves deterministically from one state to the next, it either reaches a goal or revisits a state it's already been in — and a revisit means it will loop forever. A set of seen states detects that loop; fast/slow pointers detect it in O(1) space.
The shape
If you ever see the same state twice, the future repeats — so:
- Seen-set: record each state; stop on the goal (success) or on a repeat (cycle). O(states) time and space.
- Floyd's tortoise & hare: a slow pointer (1 step) and fast pointer (2 steps) over
next(); if they meet, there's a cycle — O(1) space.
The problem
- Happy Number — repeatedly replace
nwith the sum of squares of its digits; it reaches 1 (happy) or falls into a fixed cycle. A seen-set spots the repeat; fast/slow does it without storing states.
Key takeaways
- Deterministic next-state ⇒ either a goal or a cycle — and a repeated state proves the cycle.
- Seen-set is the simplest detector (O(n) space); fast/slow trades it down to O(1).
- The same pattern appears on linked lists (Linked List Cycle) and any functional graph.
- Why interviewers like it: it tests whether you recognize "this will loop" and know two ways to catch it.
Problem: Happy Number.