Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Book a call

Coding · Two pointers

Fast and slow pointers

Lesson · 11 min read · Two pointers · Fast and slow pointers

Two pointers on the same path, one moving twice as fast. If there's a loop they meet in it, and a second walk finds where the loop starts. No memory needed.

A path you can only follow

Every module so far had both pointers on an array you could index into. This one's different. You've got a rule that takes you from one value to the next (the next node in a list, nums[i] from index i, the sum of the squares of the digits of a number) and you can only follow it forwards. If the values come from a finite set the path has to repeat at some point, and after that it goes round a loop for ever. The question's usually whether there's a loop, or where it starts.

You could keep a set of everything you've seen and that answers both questions, but it costs you O(n) memory. Floyd's method gets the same answers with two pointers and nothing else, and I think that's a big part of why interviewers like asking about it.

Why the fast one catches the slow one

You put both pointers at the start, and on every step the slow one follows the rule once while the fast one follows it twice. If the path comes to an end (a node with no next, or a value that maps to itself) then the fast one's going to get there first and you've got your answer. If there's a loop they'll both end up in it, and from then on the fast one gains exactly one place on every step. It can't jump over the slow one when it's only one place behind, so they're bound to meet before the slow one has gone round once.

Floyd

meetAndFind(start)

  1. slow = next(start) and fast = next(next(start)).
  2. While slow ≠ fast: slow = next(slow) and fast = next(next(fast)).
  3. Set a = start. While a ≠ slow: a = next(a) and slow = next(slow).
  4. Return a, the first value on the loop.

Finding where the loop starts

The second walk is the part people find surprising. Say the path into the loop is a steps long, the loop's c long, and the pointers met b steps past the start of the loop. The fast one's gone twice as far as the slow one, and the extra distance is a whole number of laps, so a + b is a multiple of c. That means walking a more steps from the meeting point brings you exactly to the start of the loop. You don't know a, but you don't need to, because a pointer walking from the start gets there in a steps as well. So you move both one step at a time and they meet at the start of the loop.

Here's what that looks like on the duplicate number problem, where index i points to nums[i] and the repeated value turns out to be the start of the loop.

Index 0 is the right place to start because the values run from 1 to n, so nothing points to 0. That guarantees it's on the path into the loop and not on the loop itself.

Following i → nums[i] in [1, 3, 4, 2, 2] from index 0.

  1. Step 1 / 8
    nums
    1031slow4223fast24
    slow1fast3

    Index i points to nums[i]. From 0 the path is 0 → 1 → 3 → 2 and so on. slow takes one step and fast takes two.

  2. Step 2 / 8
    nums
    10314223slow24fast
    slow3fast4

    slow moves to 3 and fast jumps two arrows to 4.

  3. Step 3 / 8
    nums
    103142slow2324fast
    slow2fast4

    slow moves to 2 and fast jumps two arrows to 4.

  4. Step 4 / 8
    nums
    1031422324slow/fast
    slow4fast4

    They've met at index 4, which is somewhere inside the cycle.

  5. Step 5 / 8
    nums
    10a31422324slow
    a0slow4

    Put one pointer back at 0 and leave the other at the meeting point. Now both take one step at a time.

  6. Step 6 / 8
    nums
    1031a42slow2324
    a1slow2

    a moves to 1 and slow moves to 2.

  7. Step 7 / 8
    nums
    10314223a24slow
    a3slow4

    a moves to 3 and slow moves to 4.

  8. Step 8 / 8
    nums
    103142a/slow2324
    a2slow2

    They meet at 2. That's the start of the cycle and the repeated value.

When the next value is worked out, not stored

The rule doesn't have to be a pointer sitting in memory. For a happy number the next value is the sum of the squares of the digits and you work it out each time you need it. Every number from 1,000 up gets smaller in one step and everything below 1,000 stays below 1,000, so the path has to repeat somewhere, and either it gets to 1 and stays there or it goes round a loop. You'd run the two pointers and then check whether it was at 1 that they met.

TimeO(λ + μ)
SpaceO(1)

λ is the length of the loop and μ the length of the path into it. For an array of n + 1 values both are at most n + 1, so it's O(n).

Problems in this module