Opening your learning path
Progress is saved as you study.
Opening your learning path
Progress is saved as you study.
The Fast & Slow (Cycle Detection) pattern applies when you need the Fast & Slow (Cycle Detection) technique within the Two Pointers pattern. Its time complexity is O(n) and space complexity O(1). It is used in 4 problems on Thita, including Find the Duplicate Number, Happy Number and Is Subsequence. Common variations are String Comparison with Backspaces and String Reversal.
Master Floyd's tortoise and hare algorithm for cycle detection. Detect cycles in linked lists and find duplicate numbers.
Fast & Slow (Cycle Detection) is one of the 7 subpatterns of the Two Pointers pattern, which covers fast-slow, converging, expanding from center, and in-place modification techniques. The whole pattern is about 3 hours of study. This subpattern is a core technique: expect it to come up directly in interviews.
Master the two pointers technique including fast-slow pointers, converging pointers, and expanding from center. Essential for array, string, and linked list problems in coding interviews. Problems in this subpattern are usually searched for as floyd cycle detection, fast slow pointers, tortoise hare, linked list cycle, find duplicate, leetcode 141.
Read the theory for Fast & Slow (Cycle Detection), then work the problems attached to it in the browser editor. Your solution runs against the problem's test cases, and the AI coach offers a hint about the technique you are missing rather than a finished solution. Progress is tracked per subpattern, so the Two Pointers tracker shows this one as covered once you have solved its problems.
Fast & Slow (Cycle Detection) is one lesson in a 16-pattern DSA course. If you are preparing end to end, work the interview-critical patterns first and use the pattern sheet as the checklist; if you are here for one technique, the Two Pointers guide is the shortest path back to the rest of it.
4 problems, easiest first.
Imagine you and a friend are walking around a circular track. You start together, but your friend walks twice as fast as you. If the track is a perfect circle and you both keep walking, eventually, your friend will lap you and catch up again. But if the track is a straight line, your friend will just keep getting farther ahead and never meet you again. This is the heart of the Fast & Slow Pointers (also called the "Tortoise and Hare") cycle detection pattern.
Fast and slow pointers on a list whose tail loops back to node 3. Inside the loop the gap fast must close shrinks by one per step (2, 1, 0), so they meet at node 5 and prove a cycle.
This pattern is incredibly useful when you need to detect cycles or repeated patterns in data structures like linked lists or even arrays. It's like having two detectives following clues at different speeds—if there's a loop, the faster one will eventually catch up to the slower one inside the loop. If not, the faster one will reach the end and stop.
You'll often use this pattern when:
Think of it as a clever way to "see the future" of a process by racing two markers through it at different speeds. If they ever meet, you've found a loop!
Let's break down how the Fast & Slow Pointers pattern works, step by step:
slow and fast.slow pointer moves one step at a time, while the fast pointer moves two steps at a time.Imagine a circular race track:
Think of it like reading a book with two bookmarks—one moves one page at a time, the other two pages. If the book is circular (pages loop back), the bookmarks will overlap. If not, the faster one finishes first.
The pattern works because, in a cycle, the distance between the two pointers reduces by one at each step (since fast moves two steps and slow one). Eventually, the gap closes, and they meet.
Let's build a mental model for using Fast & Slow pointers:
slow and fast pointers at the starting position.slow one step.fast two steps.slow and fast meet, a cycle exists.fast reaches the end, there's no cycle.head is null, return false (no cycle).Tip: Always check that fast and fast->next (or their array equivalents) are valid before moving them, to avoid errors.
Let's look at two classic problems from the database: Linked List Cycle and Find the Duplicate Number.
1// Definition for singly-linked list.
2struct ListNode {
3 int val;
4 ListNode *next;
5 ListNode(int x) : val(x), next(nullptr) {}
6};
7
8// Function to detect cycle in a linked list
9bool hasCycle(ListNode *head) {
10 // Initialize both pointers at the head
11 ListNode *slow = head;
12 ListNode *fast = head;
13
14 // Traverse the list
15 while (fast != nullptr && fast->next != nullptr) {
16 slow = slow->next; // Move slow by 1
17 fast = fast->next->next; // Move fast by 2
18
19 // If they meet, there's a cycle
20 if (slow == fast) {
21 return true;
22 }
23 }
24 // If fast reaches the end, no cycle
25 return false;
26}Explanation:
slow moves one node, fast moves two.fast will eventually catch up to slow.fast will hit the end (nullptr).1// Function to find the duplicate number in an array using cycle detection
2int findDuplicate(vector<int>& nums) {
3 // Think of the array as a linked list where nums[i] is the next pointer
4 int slow = nums[0];
5 int fast = nums[0];
6
7 // Phase 1: Find intersection point
8 do {
9 slow = nums[slow]; // Move slow by 1 step
10 fast = nums[nums[fast]]; // Move fast by 2 steps
11 } while (slow != fast);
12
13 // Phase 2: Find entrance to the cycle (duplicate number)
14 slow = nums[0];
15 while (slow != fast) {
16 slow = nums[slow];
17 fast = nums[fast];
18 }
19 return slow;
20}Explanation:
Let's think about this step by step.
Problem Recap:
Given an array of n + 1 integers where each integer is between 1 and n, find the duplicate number. Don't modify the array and use only constant extra space.
nums[0], you'll eventually revisit a number—the duplicate—because there are more numbers than possible unique values.slow and fast.slow by one step (slow = nums[slow]).fast by two steps (fast = nums[nums[fast]]).slow to the start.Refer to the code in the previous section. Each step follows the pattern exactly, making it both efficient and elegant.
Signals to Use This Pattern:
Aha! Moments:
Debugging Tips:
Common Misconceptions:
Memory Trick:
By mastering the Fast & Slow Pointers pattern, you'll unlock elegant solutions to many tricky cycle and repeat detection problems—just like a detective who always catches up to the culprit!