Micro-questions over the fast & slow pointers pattern. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.


A. The idea

1. Give the hallway analogy.

Answer

One person walks normally, another runs twice as fast. If there is a loop, the faster person eventually catches the slower one; if there is not, the faster person reaches the end first.

2. State the pattern.

Answer

Walk two pointers through a structure at different speeds — one step versus two steps.

3. What is it formally called?

Answer

Floyd’s Tortoise and Hare algorithm.

4. What is lapping?

Answer

The fast pointer overtaking the slow one inside the cycle — the faster runner lapping the slower on a circular track.


B. Cycle detection

5. Write the loop.

Answer
slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        return True
return False

6. Why is the guard while fast and fast.next?

Answer

The fast pointer takes two steps, so both the current node and its successor must exist before moving. Checking only fast crashes on the last node.

7. Why must they meet if a cycle exists?

Answer

Once both are inside the cycle, the gap between them shrinks by exactly one node every step, so it must eventually hit zero.

8. Trace 1→3→5→7→9→5.

Answer

slow: 1, 3, 5, 7, 9, 5…; fast: 1, 5, 9, 7, 5… After 3 steps both are at node 5 — cycle detected.


C. Versus a hash set

9. What is the hash-set alternative?

Answer

Keep a set of visited nodes — if node in visited: return True. Simpler to reason about.

10. Why is the pointer version worth knowing anyway?

Answer

Same time with space instead of — which is the entire reason this pattern exists rather than always reaching for a set.


D. Beyond linked lists

11. What does the pattern generalise to?

Answer

Any sequence generated by repeatedly applying a function to a value — anywhere you can compute the next element deterministically.

12. How does happy number use it?

Answer

get_next is the sum of the squares of the digits. Run slow one step and fast two until they meet; the number is happy iff the meeting value is 1.

13. How does find-the-duplicate use it?

Answer

An array of length with values in — treat array values as implicit next pointers. A duplicate value means two indices point at the same place, which is a cycle.

14. How do you find the cycle’s entrance?

Answer

After the meeting, reset one pointer to the start and advance both one step at a time. They meet at the entrance.

15. Why does that work?

Answer

By the distance algebra of the meeting point: the distance from the head to the entrance equals the distance from the meeting point to the entrance, going around the cycle.


E. Trade-offs

16. What does the basic algorithm not tell you?

Answer

Where the cycle starts — only whether one exists. The entrance needs the extra phase above.

17. What is the precondition?

Answer

A well-defined, deterministic “next” function.

18. When is the hash set preferable?

Answer

For small inputs, or when memory is not a concern — it is clearer to reason about and easier to get right.

19. What are the costs?

Answer

time, space.

20. Summarise the pattern in one sentence.

Answer

Run two pointers at different speeds and let the faster one lap the slower — cycle detection in constant space, on anything with a next function.


Scorecard

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to LeetCode Patterns — University-Style Teaching Notes