Dashboard/Coding patterns/02. Fast and Slow Pointers

CODING PATTERNS · LESSON 2 OF 28 · 32 MIN VIDEO · 10 PROBLEMS

Fast and Slow Pointers

Module Progress (0 / 10 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (32 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

Fast and Slow Pointers — How the Pattern Works

The Fast and Slow Pointers pattern (Floyd's Tortoise and Hare algorithm) traverses a linked structure or deterministic state-transition graph using two pointers advancing at a fixed 2:1 speed ratio: slow steps 1 link per iteration while fast steps 2 links. In an acyclic chain of length n, fast reaches the end after floor(n / 2) iterations, leaving slow positioned at the exact midpoint in a single pass. In a cyclic chain, once both pointers enter the cycle, fast reduces the modular backward gap to slow by 2 - 1 = 1 node per step, guaranteeing collision inside the cycle without skipping over slow and reducing O(n) hash-set space or multi-pass counting to O(n) time and O(1) auxiliary space.

WHEN TO USE THIS PATTERN
  • Singly or circular linked list problems asking to detect a cycle, compute cycle length, remove a cycle, or locate the middle node using O(1) extra memory.
  • Symmetric linked list operations (palindrome check, maximum twin sum, list folding) where locating the midpoint enables reversing the second half in place.
  • Implicit functional graphs where every state x deterministically maps to one next state f(x) (such as digit-square sums or modular jump arrays (i + nums[i]) % n), reducing state repetition to cycle detection.
  • Read-only array duplicate problems with n + 1 integers in [1, n], where treating values as next-index pointers (i -> nums[i]) maps the duplicate number to a cycle's entrance node.
COMMON INTERVIEW PITFALLS
  • Dereferencing fast.next.next without guarding while fast and fast.next: first, causing a null-pointer AttributeError on empty lists or odd/even list tails.
  • Comparing slow.val == fast.val instead of object identity slow is fast on linked list nodes, which triggers false-positive collisions whenever distinct nodes hold equal values.
  • Misaligning the midpoint on even-length lists: starting slow = fast = head stops slow on the second middle node (index n // 2), whereas splitting into two disjoint lists requires stopping at index (n // 2) - 1.
  • Accepting 1-node self-loops or mixed-direction edges in circular array problems instead of verifying slow != step(slow) and uniform jump signs (sign * nums[x] > 0).
Floyd's Two-Phase Cycle Detection & EntranceDetect whether a linked list or functional graph contains a cycle, and optionally recover the exact node where the cycle starts in O(1) space.
def detect_cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None
Single-Pass Midpoint & In-Place Second-Half ReversalFind the middle node of an acyclic linked list (second middle on even lengths) and reverse the back half in place for symmetric comparison.
def reverse_second_half(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    prev = None
    while slow:
        nxt = slow.next
        slow.next = prev
        prev, slow = slow, nxt
    return prev

01. Happy Number

Optimal Target: O(log n) time · O(1) space

Given a positive integer n, repeatedly replace the number with the sum of the squares of its base-10 digits. Return True if this sequence eventually reaches 1 (defining a happy number), or False if it enters an infinite cycle that does not contain 1.

EXAMPLE 1
Input: n = 19
Output: True
Explanation: 1^2 + 9^2 = 82 -> 8^2 + 2^2 = 68 -> 6^2 + 8^2 = 100 -> 1^2 + 0^2 + 0^2 = 1, terminating at the fixed point 1.
EXAMPLE 2
Input: n = 2
Output: False
Explanation: The digit-square sequence 2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 enters a closed 8-state cycle without ever reaching 1.
ARCHITECTURE / DATA FLOW DIAGRAM
1982681001
AUTOMATED TEST SUITE
Test Case 1
Input: 19
Expected: True
Test Case 2
Input: 2
Expected: False
Test Case 3
Input: 1
Expected: True
Pattern Trigger Hint ("How to Spot It")

one next value each + a repeat → fast and slow

Python 3.14 Runtime Ready

Click ▶ Run Tests (or press ⌘+Enter) to execute is_happy against all 3 test cases in WebAssembly Python.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

Inside the loop, how many nodes does fast gain on slow with each step?