Why the Tortoise and the Hare Algorithm Works
Demystifying Floyd's Cycle Detection Algorithm
I was recently asked by a mentee about the Tortoise and Hare algorithm, and I realized that many people find it confusing. I remember being puzzled by it myself when I first encountered it. In this article, I'll try to clarify how this algorithm works and why it's effective for cycle detection.
The Problem: Cycle Detection
First, let's understand the problem the algorithm addresses. The cycle detection problem involves determining whether a linked structure (like a linked list) contains a cycle. In other words, we need to check if there's a way to start from a node and follow a sequence of links that eventually loops back to the same node.
A straightforward solution is to traverse the linked list while keeping track of the nodes we've visited using a hash table (or a set). If we reach a node we've seen before, we know there's a cycle. If we reach the end (a null pointer) without encountering a repeated node, there's no cycle.
This method works fine and has a time complexity of O(N), where N is the number of nodes, but it requires O(N) additional space to store the visited nodes.
Introducing the Tortoise and Hare Algorithm
The Tortoise and Hare algorithm, also known as Floyd's Cycle Detection Algorithm, offers a way to detect cycles using only constant O(1) space, while maintaining O(N) time complexity.
How It Works
Two Pointers: We use two pointers to traverse the linked list:
Tortoise (Slow Pointer): Moves one node at a time.
Hare (Fast Pointer): Moves two nodes at a time.
Cycle Detection:
If there's no cycle: The hare will reach the end of the list (a
nullpointer) before the tortoise.If there's a cycle: The hare will eventually lap the tortoise, and they will meet at some node within the cycle.
Understanding Why It Works
Intuitive Explanation
Imagine you and a friend are running on a circular track:
You (Tortoise): Run at a steady pace (one lap per hour).
Your Friend (Hare): Runs twice as fast (two laps per hour).
If you both start at the same point, your friend will lap you after one hour because they're running twice as fast. Even if you start at different points, your friend will eventually catch up to you because they're moving faster on the same loop.
In the context of a linked list with a cycle, the hare moves through the nodes twice as fast as the tortoise. If there's a cycle, the hare will "lap" the tortoise and they will meet inside the cycle.
Why the Hare Doesn't Overjump the Tortoise
A common question is: Why doesn't the hare skip over the tortoise without meeting it?
Since the hare moves two steps for every one step the tortoise takes, the distance between them decreases by one node on each move:
If the hare is K nodes behind the tortoise, after each move, the gap reduces by one.
Eventually, the hare will catch up to the tortoise.
In other words, the speed of the hare relative to the speed of the tortoise, is only one node per iteration. It is as if the tortoise is standing in its place while the hare is moving one node at a time. Because the hare gets closer (in a cycle) or further (without a cycle) only one node at a time, there is no way for the hare to skip over the tortoise.
Where Do They Meet?
If there is a cycle, the tortoise and hare will meet somewhere within the cycle. The exact node where they meet depends on the length of the non-cyclic part of the list and the length of the cycle.
Finding the Start of the Cycle
Once we've detected a cycle (when the tortoise and hare meet), we might want to find the node where the cycle begins.
The Algorithm
Reset the Tortoise: Move the tortoise pointer back to the head of the list.
Move Both Pointers at the Same Speed: Now, both the tortoise and hare move one step at a time.
Point of Intersection: The node where they meet again is the start of the cycle.
Why Does This Work?
Let's break it down mathematically:
Let:
L be the length of the non-cyclic part (nodes before the cycle starts).
C be the length of the cycle.
M be the distance from the start of the cycle to the point where the tortoise and hare first meet within the cycle.
At the first meeting point:
The tortoise has traveled L + M steps.
The hare has traveled L + M + N * C steps, where N is the number of full cycles the hare has completed (N ≥ 1).
Since the hare moves twice as fast, Hare's distance = 2 * (Tortoise's distance):
2(L + M) = L + M + N * CSimplify the equation:
2L + 2M = L + M + N * C
=> (2L - L) + (2M - M) = N * C
=> L + M = N * CThis means L + M is a multiple of C.
When we reset the tortoise to the head and move both pointers one step at a time:
The tortoise moves L steps to reach the start of the cycle.
The hare, starting from the meeting point, will also move L steps (since it's N * C - M, which simplifies to L due to the earlier equation), and they will meet at the cycle's starting node.
Intuitive Explanation
Let M be the distance from the start of the cycle to the point where the tortoise and hare first meet within the cycle. By moving tortoise back to the start, we are kind of resetting the race. But this time, we are giving the hare a head start of exactly M positions. What it means is that now tortoise and hare will meet M positions sooner, which is exactly where the start of the cycle is.
Applications Beyond Linked Lists
The Tortoise and Hare algorithm isn't limited to linked lists. It can be applied to any scenario where we can model the problem as moving through states with possible cycles.
Examples
1. Find the Duplicate Number
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive. There is only one repeated number in nums, return this repeated number.
Constraints:
You must solve the problem without modifying the array
numsand use only constant extra space.
Solution:
Modeling as a Linked List: Treat the array as a linked list where each index is a node, and the value at each index points to the next node.
Applying Tortoise and Hare: Use the cycle detection algorithm to find the duplicate number, which corresponds to the start of the cycle.
LeetCode Problem: Find the Duplicate Number
2. Happy Number
A happy number is a number defined by the following process:
Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle that does not include 1.
Those numbers for which this process ends in 1 are happy.
Return true if n is a happy number, and false if not.
Solution:
Modeling the Process: Each number generated is a state, and we can consider the process as moving from one state to another.
Applying Tortoise and Hare: Use the algorithm to detect if there's a cycle (which would mean the number is not happy).
LeetCode Problem: Happy Number
Is This Algorithm Useful for Interviews?
Yes and No.
Yes:
Demonstrates Deep Understanding: Knowing the Tortoise and Hare algorithm shows that you have a solid grasp of algorithmic techniques and can apply them to solve problems efficiently with optimal space complexity.
Useful for Certain Problems: Some interview problems are best solved using this algorithm, especially when space constraints are tight.
No:
Challenging to Derive on the Spot: Unless you're familiar with the algorithm beforehand, it's unlikely you'll come up with it during an interview under time pressure.
Acceptable Alternatives: Interviewers generally accept solutions that use hash tables to detect cycles, even if they use O(N) space, as long as the time complexity is acceptable and the solution is correct.
My Recommendation
Familiarize Yourself: Even if you don’t stumble upon a cycle detection problem or won’t use the algorithm in your solution, it's beneficial to understand this strategy.
Communicate with the Interviewer: If space complexity is a concern, mention that you know an O(1) space solution using the Tortoise and Hare algorithm.
Use the Best Approach You Know: If you're unsure about implementing the algorithm correctly, it's better to use a method you're confident with, like using a hash table to track visited nodes.
Conclusion
The Tortoise and Hare algorithm is a clever technique for detecting cycles with constant space complexity. Understanding why it works can deepen your grasp of algorithmic concepts and might give you an edge in interviews.
Remember:
Cycle Detection: Two pointers moving at different speeds can detect cycles when they meet.
Finding Cycle Start: Resetting one pointer to the head and moving both at the same speed leads to the cycle's entry point.
Applications: Beyond linked lists, the algorithm applies to any sequence of states with potential cycles.
Stay curious and happy coding!
Nurbo
Batch Mentorship Session Bookings Available Now
By popular request I just enabled batch-bookings for my mentorship sessions.
If you book 10 sessions at once, you will save $200. Just follow this link to book all 10 sessions or just book the first of the 10 and you can book the rest later.