# 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.

![](https://cdn.hashnode.com/uploads/covers/66da7e821dd4c5ccda1fb89f/f33d587c-ce32-45e6-a94b-8425886c3d78.png align="center")

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/](https://leetcode.com/problems/happy-number/) |
| Linked List Cycle | [https://leetcode.com/problems/linked-list-cycle/](https://leetcode.com/problems/linked-list-cycle/) |
| Is Subsequence | [https://leetcode.com/problems/is-subsequence/](https://leetcode.com/problems/is-subsequence/) |
| Find the Duplicate Number | [https://leetcode.com/problems/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.

![](https://cdn.hashnode.com/uploads/covers/66da7e821dd4c5ccda1fb89f/c3431f22-796a-4dcd-b70e-3bd7697dd915.png align="center")

### 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

```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

```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.

![](https://cdn.hashnode.com/uploads/covers/66da7e821dd4c5ccda1fb89f/da028fc3-255e-426c-9ff8-ce1f871c631f.png align="center")

### 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

```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

```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

```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

```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

```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

```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