Pattern: Fast & Slow pointers — Problem Statement & Solution Guide
Problem Description
You are given an integer array next of length n that encodes a singly linked list. The head of the list is node 0. For each i (0 ≤ i < n), next[i] is either -1, meaning node i has no successor, or an integer j (0 ≤ j < n) indicating that node i points to node j. The list may contain a cycle. Your task is to return the index of the node where the cycle first appears (the entry point of the cycle). If the list does not contain any cycle, return -1. The algorithm must run in O(n) time and use O(1) additional memory, i.e., it should be based on the fast‑slow (Floyd’s Tortoise and Hare) pointer technique.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Pattern: Fast & Slow pointers"
WHY DOES IT MATTER?
Fast‑and‑slow pointers provide a deterministic, O(1)‑space method to uncover hidden cycles, a scenario that appears in memory leak detection, network routing loops, and concurrency deadlock analysis. Mastery of this pattern signals a candidate’s ability to reason about pointer dynamics and mathematical invariants.
OPTIMIZATION CHALLENGE
The breakthrough is realizing that you don’t need to remember every visited node; the relative speed difference creates a guaranteed collision inside any loop, turning a potentially O(n)‑space problem into a constant‑space one.
REAL-WORLD CONNECTION
Think of a runner (slow) and a cyclist (fast) on a circular track. If the cyclist starts together and runs twice as fast, they will eventually meet. Resetting the runner to the start line and keeping the cyclist where they met mirrors how distributed systems detect looped message paths without storing the entire path history.
During an interview, first write the two‑pointer loop to detect a meeting, then add the second phase to locate the entry. Keep variable names clear (slow, fast, head) and comment the invariant: after detection, distance from head equals distance from meeting point to entry.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The fast‑and‑slow pointer technique, also known as Floyd’s Tortoise and Hare algorithm, leverages two traversals moving at different speeds to detect cycles in O(n) time with O(1) extra space. The intuition is that if a cycle exists, the faster pointer will eventually lap the slower one inside the loop, guaranteeing a meeting point regardless of the list length. Once the pointers meet, resetting one pointer to the head and moving both at the same speed leads them to converge at the cycle’s entry node, because the distance from the head to the entry equals the distance from the meeting point to the entry when traversed at equal speed.
A naive solution would store every visited index in a hash set and stop when a repeat is seen. While conceptually simple, this approach incurs O(n) additional memory, which becomes prohibitive for massive linked structures or memory‑constrained environments. Moreover, hash‑set operations add constant‑factor overhead that can affect runtime on tight time limits. The fast‑and‑slow pointer paradigm eliminates the need for auxiliary storage by exploiting deterministic pointer movement, delivering the optimal linear‑time, constant‑space solution.
The optimal paradigm is rooted in the mathematical properties of modular arithmetic on the cycle length. If the non‑cyclic prefix has length μ and the cycle length is λ, after μ steps the slow pointer enters the cycle, and after k·λ steps the fast pointer catches up. Solving the equations for the meeting point yields the guarantee that moving both pointers from head and meeting point at unit speed meets exactly at the entry after μ steps. This elegant proof underpins why the algorithm is both correct and optimal.
Interview Questions on This Problem
Q1How would you modify Floyd’s algorithm to return the length of the cycle instead of the entry point?
After the first meeting of fast and slow pointers, keep one pointer stationary and move the other until it meets the stationary pointer again, counting steps; the count equals the cycle length λ.
Q2Can you detect a cycle in a directed graph represented by an adjacency list using the fast‑and‑slow pointer technique?
No, Floyd’s algorithm relies on a single‑path traversal (each node has at most one outgoing edge). In a general directed graph you need DFS with recursion stack or Kahn’s topological sort to detect cycles.
Q3Why does resetting one pointer to the head after detection guarantee convergence at the cycle entry?
At the meeting point, the slow pointer has traveled μ + k·λ steps and the fast pointer 2·(μ + k·λ). The distance from head to entry is μ, and the distance from meeting point to entry is also μ modulo λ, so moving both at equal speed makes them meet after μ steps exactly at the entry.
Examples
Input
[1,2,3,4,5,2,-1]
Output
2
Explanation: The list is 0→1→2→3→4→5→2→... . Starting from node 0, the slow pointer moves one step each iteration while the fast pointer moves two steps. They first meet inside the cycle after several moves. Resetting the slow pointer to the head and moving both one step at a time makes them meet again at node 2, which is the entry of the cycle. Hence the answer is 2.
Input
[1,2,3,4,-1]
Output
-1
Explanation: The list is 0→1→2→3→4→null. The fast pointer reaches -1 (null) before the slow pointer meets it, indicating there is no cycle. Therefore the output is -1.
Input
[2,0,4,5,3,2]
Output
2
Explanation: The list follows 0→2→4→3→5→2→... . After the first phase of the algorithm the fast and slow pointers meet somewhere inside the loop. Moving one pointer back to the head and advancing both one step at a time makes them converge at node 2, the first node that repeats. Thus the cycle starts at index 2.
Constraints
- 1 <= next.length <= 100000
- Each next[i] is either -1 or an integer in the range [0, next.length - 1]
- The list is defined to start at index 0
Optimal Approach & Strategy
Use two pointers moving at different speeds (slow = 1 step, fast = 2 steps) to detect a meeting, then reset one pointer to the head and advance both one step at a time to locate the entry.
Brute Force Approach
Store every visited index in a hash set and stop when you encounter a duplicate; the duplicate index is the cycle entry.
Verified Code Solutions
function findCycleEntry(next) {
if (!next || next.length === 0) return -1;
let slow = 0;
let fast = 0;
// First phase: detect cycle
while (fast !== -1 && next[fast] !== -1) {
slow = next[slow];
fast = next[next[fast]];
if (slow === fast) break;
}
if (fast === -1 || next[fast] === -1) return -1; // No cycle
// Second phase: find entry point
slow = 0;
while (slow !== fast) {
slow = next[slow];
fast = next[fast];
}
return slow;
}
// Example usage:
const next = [1,2,3,4,5,2,-1];
console.log(findCycleEntry(next)); // 2#include <vector>
#include <iostream>
int findCycleEntry(const std::vector<int>& next) {
int n = next.size();
if (n == 0) return -1;
int slow = 0;
int fast = 0;
// First phase: determine if a cycle exists
while (fast != -1 && next[fast] != -1) {
slow = next[slow];
fast = next[next[fast]];
if (slow == fast) break;
}
if (fast == -1 || next[fast] == -1) return -1; // No cycle
// Second phase: find entry point
slow = 0;
while (slow != fast) {
slow = next[slow];
fast = next[fast];
}
return slow;
}
int main() {
std::vector<int> next = {1,2,3,4,5,2,-1};
std::cout << findCycleEntry(next) << std::endl; // Output: 2
return 0;
}
public class Solution {
// Function to find the entry point of a cycle in a linked list represented by the array 'next'.
// If there is no cycle, return -1.
public int findCycleEntry(int[] next) {
if (next == null || next.length == 0) return -1;
int slow = 0;
int fast = 0;
// First phase: detect cycle
while (fast != -1 && next[fast] != -1) {
slow = next[slow];
fast = next[next[fast]];
if (slow == fast) break;
}
if (fast == -1 || next[fast] == -1) return -1; // No cycle
// Second phase: find entry point
slow = 0;
while (slow != fast) {
slow = next[slow];
fast = next[fast];
}
return slow;
}
public static void main(String[] args) {
int[] next = {1,2,3,4,5,2,-1};
Solution sol = new Solution();
System.out.println(sol.findCycleEntry(next)); // 2
}
}
def find_cycle_entry(next):
if not next:
return -1
slow = 0
fast = 0
# First phase: detect cycle
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
if slow == fast:
break
if fast == -1 or next[fast] == -1:
return -1 # No cycle
# Second phase: find entry point
slow = 0
while slow != fast:
slow = next[slow]
fast = next[fast]
return slow
# Example usage:
next = [1,2,3,4,5,2,-1]
print(find_cycle_entry(next)) # 2
function findCycleEntry(next) {
if (!next || next.length === 0) return -1;
let slow = 0;
let fast = 0;
// First phase: detect cycle
while (fast !== -1 && next[fast] !== -1) {
slow = next[slow];
fast = next[next[fast]];
if (slow === fast) break;
}
if (fast === -1 || next[fast] === -1) return -1; // No cycle
// Second phase: find entry point
slow = 0;
while (slow !== fast) {
slow = next[slow];
fast = next[fast];
}
return slow;
}
// Example usage:
const next = [1,2,3,4,5,2,-1];
console.log(findCycleEntry(next)); // 2
Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.