Two Points (Fast & Slow Pointers, Cyclic detection)

The pattern

Two pointers walk the same sequence at different speeds. One takes a single step per iteration (the tortoise), the other takes two (the hare). That's it. Everything interesting follows from the speed difference.

The pattern applies whenever you have a successor function — a rule that maps each state to exactly one next state:

• A linked list node → node.next

• A number → sum of squares of its digits

• An array index i → nums[i]

If the set of reachable states is finite and every state has exactly one successor, the walk must eventually revisit a state. Pigeonhole principle: you can only visit so many distinct states before you're forced to repeat one. And once you repeat one, you're stuck in a loop forever, because the successor is deterministic.

Why the pointers meet

Slow moves 1 step per iteration, fast moves 2. Once both are inside the cycle, the gap between them shrinks by exactly 1 each iteration. A gap that decreases by 1 every step and lives in a finite cycle must hit zero. They cannot jump over each other.

Contrast that with fast moving 3 steps: the gap shrinks by 2 per iteration and can skip past zero, so a meeting isn't guaranteed on the first pass around. Speed 2 is the choice that makes the proof trivial.

• The constraint O(1) space next to any of the above. That constraint is the pattern announcing itself — the hash-set solution is always easier and always O(n) space.

Problem	Link
Happy Number	https://leetcode.com/problems/happy-number/
Linked List Cycle	https://leetcode.com/problems/linked-list-cycle/
Is Subsequence	https://leetcode.com/problems/is-subsequence/
Find the Duplicate Number	https://leetcode.com/problems/find-the-duplicate-number/

---

Problem 1 — Happy Number (Easy)

Repeatedly replace a number with the sum of the squares of its digits. Return true if the process reaches 1.

How it maps to the pattern

The successor function is n → sum of squares of digits. The key insight is that the state space is finite and small. For any 3-digit number the maximum output is 9² × 3 = 243. Any number with more digits shrinks rapidly, so after the first couple of steps every value lives below 243. Finite states plus a deterministic successor means the sequence must cycle.

So there are exactly two outcomes: the walk lands on 1 (a self-loop, since 1² = 1), or it enters some other cycle. Detecting which one is exactly the cycle-detection problem — no visited set required.

Approach

1. slow = n, fast = next(n)

2. Advance slow once, fast twice, until fast == 1 or the pointers meet

3. Return whether we stopped because we hit 1

We only need phase 1 here. The entrance of the cycle is irrelevant; we just need to know which cycle we landed in.

Python

def is_happy(n: int) -> bool:
    def next_num(x: int) -> int:
        total = 0
        while x:
            x, digit = divmod(x, 10)
            total += digit * digit
        return total

    slow, fast = n, next_num(n)
    while fast != 1 and slow != fast:
        slow = next_num(slow)
        fast = next_num(next_num(fast))
    return fast == 1

Java

public boolean isHappy(int n) {
    int slow = n, fast = nextNum(n);
    while (fast != 1 && slow != fast) {
        slow = nextNum(slow);
        fast = nextNum(nextNum(fast));
    }
    return fast == 1;
}

private int nextNum(int x) {
    int total = 0;
    while (x > 0) {
        int digit = x % 10;
        total += digit * digit;
        x /= 10;
    }
    return total;
}

Complexity

Time: O(log n). Reducing n to below 243 takes O(log n) work, since each next_num call costs O(log x) and the value collapses quickly. After that, the walk is bounded by a constant (the cycle and tail both live in a fixed 243-element space).

Space: O(1). Two integers. The hash-set version is O(log n) space.

---

Problem 2 — Linked List Cycle (Easy)

Given the head of a linked list, determine if it has a cycle.

How it maps to the pattern

This is the pattern in its purest form — the successor function is literally node.next, and the question asked is literally "is there a cycle?" Every other problem in this list is a disguised version of this one.

Approach

1. Both pointers start at the head

2. Slow advances one node, fast advances two

3. If fast (or fast.next) falls off the end, the list is acyclic — a null means no cycle exists

4. If the pointers ever hold the same node, there's a cycle

The null check is the whole implementation risk. Fast dereferences two links per iteration, so both fast and fast.next must be non-null before you move.

Python

def has_cycle(head) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Java

public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

Complexity

Time: O(n). Slow travels at most μ + λ nodes before the meeting, and both are bounded by n.

Space: O(1). Compare to the hash-set approach, which stores every visited node — O(n).

Variant worth knowing: Linked List Cycle II asks for the node where the cycle begins. That's phase 2 — reset slow to head, advance both one step at a time, and return where they meet. Same code, four extra lines.

---

Problem 3 — Is Subsequence (Easy)

Return true if string s is a subsequence of string t.

How it maps to the pattern — with a caveat

Be careful here. This is not Floyd's cycle detection. There is no cycle, no successor function, and no rho shape. It's filed under Fast & Slow because it shares the mechanical idea of two pointers advancing at different rates over the same traversal — but the rates are data-dependent rather than fixed.

The pointer over t advances on every iteration (the fast one). The pointer over s advances only on a character match (the slow one). The gap between them is the number of characters in t we've skipped.

Worth saying out loud: if you go in expecting cycle detection here, you'll waste ten minutes looking for a cycle that doesn't exist. The useful generalisation is "unequal advancement," and cycle detection is one instance of it.

Approach

1. Pointer i over s, pointer j over t, both at 0

2. Scan t once. On a match, advance i. Always advance j

3. s is a subsequence exactly when i reaches the end of s

Greedy matching is correct here: taking the earliest possible match for each character of s never eliminates a valid later match, because any solution using a later occurrence can be rewritten to use the earlier one.

Python

def is_subsequence(s: str, t: str) -> bool:
    i = 0
    for ch in t:
        if i < len(s) and s[i] == ch:
            i += 1
    return i == len(s)

Java

public boolean isSubsequence(String s, String t) {
    int i = 0, j = 0;
    while (i < s.length() && j < t.length()) {
        if (s.charAt(i) == t.charAt(j)) i++;
        j++;
    }
    return i == s.length();
}

Complexity

Time: O(n + m) where n = |s| and m = |t|. Each pointer only moves forward, so the total work is bounded by the sum of the lengths.

Space: O(1).

Follow-up: if you get many s queries against one fixed t, this becomes the wrong tool. Precompute, for each position in t and each of the 26 letters, the next occurrence — O(26m) preprocessing, then O(|s| log m) or O(|s|) per query.

---

Problem 4 — Find the Duplicate Number (Medium)

An array of n + 1 integers where each value is in the range [1, n]. Exactly one value repeats. Find it without modifying the array, in O(1) space.

How it maps to the pattern

This is the most elegant application, and the one worth building the post around. The array is secretly a linked list.

Treat each index as a node and define the successor of i as nums[i]. Since every value lies in [1, n] and indices run 0..n, every index points to a valid index. So we have a functional graph — exactly the structure the pattern needs.

Two facts make it work:

1. Index 0 is never a target. All values are ≥ 1, so nothing points to index 0. It can't be part of a cycle, which makes it a safe starting point with a genuine tail leading into the cycle.

2. The duplicate value is the node with two incoming edges. If nums[a] == nums[b] == v for a ≠ b, then node v is reachable from two different predecessors — that's the merge point of the rho, which is precisely the cycle entrance.

Finding the duplicate is finding the cycle entrance. That's why phase 2 is mandatory here, unlike in Happy Number.

Approach

1. Phase 1 — slow and fast both start at nums[0]; advance until they meet somewhere inside the cycle

2. Phase 2 — reset slow to nums[0], advance both one step at a time; they meet at the entrance

3. Return that value

Python

def find_duplicate(nums: list[int]) -> int:
    # Phase 1: find a meeting point inside the cycle
    slow = fast = nums[0]
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    # Phase 2: walk to the cycle entrance
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

Java

public int findDuplicate(int[] nums) {
    // Phase 1: find a meeting point inside the cycle
    int slow = nums[0], fast = nums[0];
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    // Phase 2: walk to the cycle entrance
    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

Complexity

Time: O(n). Both phases are bounded by μ + λ ≤ n + 1.

Space: O(1). This is the entire point of the problem. Sorting is O(n log n) and mutates the array; a frequency array or hash set is O(n) space; only Floyd's satisfies both constraints simultaneously.

---

Summary

Problem	Successor function	Phase 2 needed?	Time	Space
Happy Number	sum of squares of digits	No — only which cycle matters	O(log n)	O(1)
Linked List Cycle	node.next	No (yes for Cycle II)	O(n)	O(1)
Is Subsequence	not cycle detection — unequal rates	N/A	O(n + m)	O(1)
Find the Duplicate	i → nums[i]	Yes — the answer is the entrance	O(n)	O(1)

The takeaway: the pattern isn't really about linked lists. It's about any deterministic walk over a finite state space. Once you learn to spot the successor function hiding inside a problem — digit sums, array indices, node pointers — the O(1)-space solution writes itself.

Common mistakes

• Forgetting the fast != null && fast.next != null guard and dereferencing null

• Starting both pointers at the head and using a while (slow != fast) loop — it exits immediately on the first iteration. Use a do-while, or offset the start

• Making fast move 3 steps "to converge faster" — it doesn't guarantee a meeting

• Skipping phase 2 when the problem asks where the cycle starts, not whether it exists