Seen-set cycle detection

42 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A "happy number" game: take a number, square each digit and add the squares, and repeat. 19 → 1² + 9² = 82 → 8² + 2² = 68 → 6² + 8² = 100 → 1² + 0² + 0² = 1. Once you reach 1 you stay at 1, so 19 is happy. Try 4: 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4. It came back to 4, so it will loop forever and never reach 1. 4 is not happy.

The danger is obvious when you do it by hand: how do you know when to stop? If you just keep computing, an unhappy number keeps you busy forever. You need a way to notice "I have been here before".

Build the structure, one piece at a time

The step is deterministic: from a given number you always go to the same next number. That means the moment any number appears a second time, everything after it will repeat exactly as before, forever. So "have I seen this before?" is the only question we need, and a hash set answers it in about one step.

The procedure: keep a set called seen. At each number, if it is 1, stop with "happy". If it is already in seen, stop with "not happy". Otherwise add it to seen and compute the next number. For 19:

For 4 the set grows to {4, 16, 37, 58, 89, 145, 42, 20} and then 4 arrives again, is found in the set, and we stop with "not happy". The same skeleton detects a loop in any process that moves from state to state by a fixed rule: a linked list where each node points to a next node, a robot following fixed instructions, a function applied again and again.

Why it is correct

The invariant: the set holds exactly the states visited so far. We add each state before leaving it, and never remove, so this holds at every step.

Two things need to be true. First, if we stop with "cycle", there really is one: the state we just saw is in the set, so it was visited before, and a deterministic rule will now repeat the same path. Second, we always stop. For happy numbers, a number with d digits maps to at most 81d, so any number above 243 shrinks and every number below 1000 stays below 1000; the path lives in a finite box of states, and by the pigeonhole principle a path through a finite set of m states must repeat within m + 1 steps. The same finiteness argument covers a linked list with n nodes: after n + 1 moves some node is seen twice, or the walk fell off the end.

Why it is fast

Each state is processed once: one lookup, one insert, one step of the rule. If the path has L states before it repeats or terminates, that is O(L) time and O(L) memory. For a linked list L ≤ n. The by-hand method had no bound at all, because it never knew when to stop.

When memory matters, there is a famous O(1)-space cousin: the fast and slow pointer (tortoise and hare), which detects the same cycle without storing anything. The set version is the one to reach for when you also need to know which states were visited, or when the states are numbers rather than pointers.

How to recognise it in an interview

Cues: "repeat this operation until …", "does the process terminate", "detect a loop", or any walk along "next" pointers where you are not told there is an end. The first thing to say: "The step is deterministic, so a repeated state means an infinite loop; I will keep a set of visited states and stop on the first repeat."

Happy Number is the example above. Linked List Cycle is the same with node references as the states. Find the Duplicate Number can be read as "follow index → value as a pointer" and the duplicate is where two paths enter the same loop.

02The idea in one line

Repeating a deterministic step: a repeated state means a cycle.

Reach for it when: Happy numbers, digit games, linked structures when extra memory is fine.

Cost: O(cycle length) time and space.

03The walk-through, step by step

The video works one example: Happy Number 19 → 82 → 68 → 100 → 1. These are its captions in order, so you can follow without the video or check a step you missed.

1. Repeat a deterministic step; a repeated value means a cycle, 1 means happy
2. 19 is new: add it to seen, then 1² + 9² = 82
3. Move to 82, check the set
4. 82 is new: add it to seen, then 8² + 2² = 68
5. Move to 68, check the set
6. 68 is new: add it to seen, then 6² + 8² = 100
7. Move to 100, check the set
8. 100 is new: add it to seen, then 1² + 0² + 0² = 1
9. Move to 1, check the set
10. Reached 1: the number is happy
11. The set stops any loop; values stay small, so O(log n)-ish steps

04Asked at Google

4 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Arrays & Hashing: Hash the complement, Frequency counting, Canonical key hashing, In-place index hashing, Set-start expansion.