TechPrep
Linked structures, trees and graphsReadLabPracticeCheck

Fast and slow pointers

Two runners at different speeds detect cycles and find midpoints without extra memory.

Find the Duplicate Number. nums has n + 1 integers, each in 1..n, and exactly one value repeats (possibly many times). Find it without modifying the array and with O(1) extra space.

Signals that point here

The idea

Treat i -> nums[i] as a linked list. Values are in 1..n so every arrow lands inside the array, and the duplicate value is a node with two incoming arrows: the entrance of a cycle.

Floyd's algorithm: phase 1, slow moves one hop and fast two until they meet inside the cycle. Phase 2, restart one runner at the start; moving both one hop at a time, they meet exactly at the entrance. The proof is one line of algebra; be ready to sketch it (distance to entrance equals distance from meeting point to entrance, modulo the cycle length).

def find_duplicate(nums: list[int]) -> int:
    slow = fast = nums[0]
    while True:                      # phase 1: meet inside the cycle
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    slow = nums[0]                   # phase 2: walk to the entrance
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

Complexity

O(n) time, O(1) extra space. Mention the alternatives and why the constraints exclude them: a hash set is O(n) space; sorting modifies the array; binary search on the count is O(n log n).

Pitfalls interviewers watch for

Variants worth knowing

Test it like the interviewer will

Step through it: find_duplicate([3, 1, 3, 4, 2])

Each step is recorded from an instrumented copy of the Python above, run when the site was built.

Practice

Written for this site to drill the lesson. Not reported interview questions.

  1. Return the node where a linked list's cycle begins, or null.
  2. Determine whether a number is "happy" (repeated digit-square sums reach 1).
  3. Check whether a singly linked list is a palindrome in O(1) extra space.

Check yourself

Why must a duplicate create a cycle?

Every index points somewhere inside the array, so the walk must revisit a node; the duplicate value is the node with two incoming edges, the cycle's entrance.

What changes between phase 1 and phase 2?

One runner restarts from the beginning and both move one step at a time.

Saved in this browser.