Pattern1 Practice5 Interview

Fast and Slow Pointers

GuideCode Labs

Advance pointers at different speeds to detect cycles, middles, or repeated state. Learn its decision rule, maintained state, Python cost model, and transfer from a focused drill to a full Interview Problem.

Recognize it when

Consider Fast and Slow Pointers when the prompt's constraints and required operations match this shape: Advance pointers at different speeds to detect cycles, middles, or repeated state.

On this page · Create Relative Motion

Checking your account…

Create Relative Motion

When two pointers follow the same deterministic successor at different speeds, their relative position changes without extra memory. On an acyclic chain fast reaches null; inside a cycle fast eventually laps slow.

Detect a Cycle Meeting

Advance slow one edge and fast two, checking both fast and next(fast) before dereferencing. A meeting proves both pointers are inside the cycle, though it does not yet identify the entry.

Trace the First Cycle Meeting

Reference

def pointer_meeting_trace(next_indices, head):
    slow = fast = head
    trace = []
    while fast != -1 and next_indices[fast] != -1:
        slow = next_indices[slow]
        fast = next_indices[next_indices[fast]]
        trace.append([slow, fast])
        if slow == fast: break
    return trace

Practice

Implement pointer_meeting_trace(next_indices, head). Return each [slow, fast] state through the first meeting or null termination.

def pointer_meeting_trace(next_indices, head):
    pass

Public tests

Stop at collision or null

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Find the Cycle Entry

After a meeting, place one pointer at the head and move both one step. Their equal-distance paths meet at the entry because the pre-cycle distance matches the remaining modular distance around the cycle.

Find the Cycle Entry

Reference

def cycle_entry_index(next_indices, head):
    slow = fast = head
    while fast != -1 and next_indices[fast] != -1:
        slow = next_indices[slow]
        fast = next_indices[next_indices[fast]]
        if slow == fast:
            finder = head
            while finder != slow:
                finder = next_indices[finder]
                slow = next_indices[slow]
            return finder
    return -1

Practice

Implement cycle_entry_index(next_indices, head). Return the cycle entry using Floyd's two phases, or -1 for an acyclic chain.

def cycle_entry_index(next_indices, head):
    pass

Public tests

Recover entry after meeting

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Fast Slow or a Visited Set

Use fast/slow when the state transition is deterministic and O(1) auxiliary space matters. A visited set is often easier to generalize and can report the first repeated state directly, but costs O(n) space. Both approaches take O(n) time.

Explain It in an Interview

Say: “Fast gains one step per iteration inside the cycle, so it must meet slow. Resetting one pointer makes their remaining distances to the entry equal.” Also explain the null guards. Find the Duplicate Number(opens in a new tab) models array values as successor links.

Python Version Note

Python 3.11+

The examples use the standard Python syntax and containers supported by the browser Judge; the Fast and Slow Pointers invariant is independent of a minor Python release.

Verify in Python docs

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

Operation	Average	Worst	Interview note
Fast and Slow Pointers decision loop	`O(n)`	`O(n)`	A runner moving twice as fast reaches the end when a one-step runner reaches the midpoint, without counting length first. After each loop, slow has advanced one link for every two links attempted by fast.

Space

O(1) for the focused Trace Fast and Slow Pointers implementation.

Assumptions

Fast reaches the end after twice as many link advances as slow, placing slow at the midpoint boundary. The explicit null checks stop before an invalid dereference and distinguish odd from even lengths correctly.
The bound includes real Python operations; no repeated slicing, linear list membership, or hidden sorting is treated as free.

Invariants Worth Saying Aloud

State the precise Fast and Slow Pointers invariant before coding and preserve it after every update, traversal step, or recursive return.
Both pointers follow the same deterministic successor relation.
A collision proves repeated state only under the stated successor model.
A runner moving twice as fast reaches the end when a one-step runner reaches the midpoint, without counting length first. Preserve this property after every transition.
After each loop, slow has advanced one link for every two links attempted by fast. Preserve this property after every transition.

When To Use Or Avoid Fast and Slow Pointers

Use It When

Use Fast and Slow Pointers when the prompt exposes the ordering, monotonicity, recurrence, or constraint that makes this decision safe.
Use it when both pointers follow the same deterministic successor relation.

Choose Another Tool When

Avoid Fast and Slow Pointers when its decision rule cannot eliminate work or preserve the required state.
Avoid forcing the label onto a prompt whose simpler direct scan already meets the constraints.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Moving state without a proof

Applying the pattern without proving its ordering, monotonicity, or window invariant can silently miss valid candidates.

Prevent it: Write the decision rule beside the loop and verify it against Trace Fast and Slow Pointers before optimizing.

Avoid

def middle_link_index(next_indices, head):
    pass

Use instead

def middle_link_index(next_indices, head):
    slow = fast = head
    while fast != -1 and next_indices[fast] != -1:
        slow = next_indices[slow]
        fast = next_indices[next_indices[fast]]
    return slow

Where you will hit this: Trace Fast and Slow Pointers(opens in a new tab)

Breaking the maintained state

Stops before the final two-step advance and returns the first middle node for even-length chains.

Prevent it: Use the public tests and preserve this state: Both pointers follow the same deterministic successor relation.

Avoid

def middle_link_index(next_indices, head):
    slow = fast = head
    while fast != -1 and next_indices[fast] != -1 and next_indices[next_indices[fast]] != -1:
        slow = next_indices[slow]
        fast = next_indices[next_indices[fast]]
    return slow

Use instead

def middle_link_index(next_indices, head):
    slow = fast = head
    while fast != -1 and next_indices[fast] != -1:
        slow = next_indices[slow]
        fast = next_indices[next_indices[fast]]
    return slow

Where you will hit this: Trace Fast and Slow Pointers(opens in a new tab)

Hiding Python work in the hot path

Python slicing, copying, membership in lists, or repeated sorting inside the loop can invalidate the intended complexity.

Prevent it: Count every slice, copy, sort, membership check, and container update before claiming O(n).

Avoid

def middle_link_index(next_indices, head):
    slow = fast = head
    while fast != -1 and next_indices[fast] != -1 and next_indices[next_indices[fast]] != -1:
        slow = next_indices[slow]
        fast = next_indices[next_indices[fast]]
    return slow

Use instead

def middle_link_index(next_indices, head):
    slow = fast = head
    while fast != -1 and next_indices[fast] != -1:
        slow = next_indices[slow]
        fast = next_indices[next_indices[fast]]
    return slow

Where you will hit this: Find the Duplicate Number(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.

Python More on Lists(opens in a new tab)
python-docs · checked 2026-07-27

Checking your account…