Hi there 😊 !!! Glad to see you and thank you for taking the time to give this article a look.
To stay notified about more such articles make sure you subscribe to my newsletter.
Floyd’s Tortoise and Hare Algorithm:
Floyd's Tortoise and Hare algorithm is used to detect a cycle in a sequence of iterated function values.
In layman terms it is used in problems like, detect a cycle in the linked list along with detecting the entrance of linked list.
A Few Leetcode problems that can be solved efficiently using this algorithm:
How the algrorithm works?
Declare two pointers Fast and Slow(or Hare and Tortoise)
Assuming that the cycle exists. The algorithm consists of two phases.
Phase 1:
The hare moves twice as fast as the tortoise.
Since the hare is moving faster than the tortoise it will roll at least once in the cycle to meet tortoise somewhere.
Note that there is also a probability that the tortoise rolls in the cycle at least once before they intersect/meet each other.
When the hare meets tortoise, hare wins.
Anyways, tortoise deserves a second chance :) so it gets one.
Phase 2:
To give tortoise a second chance we tell the hare to slow down and move at the same speed as the tortoise(i.e. one step at a time)
But to convince hare the tortoise is asked to start from the beginning, while the hare stays at the same place as it was at the end of the first phase(i.e. meeting place).
As a mathematical consequence they meet at the entrance of the cycle after exactly same number of steps, and the problem gets solved.
Why does the algorithm work?
Let’s analyse things a bit more naturally, and what better way could we have than to express them mathematically?
For Phase 1:
Hare moves twice as fast as tortoise.
Therefore, hare will cover twice as much distance as the tortoise before intersecting for the first time.
Mathematically,
2(D1) = D2 <--- Eqn.1
(where D1 is the distance covered by the tortoise and D2 by hare)
Consider that distance till the entrance of cycle from the beginning is F
Consider that the distance from the point of entrance of cycle to the point of first intersection is k
Consider that a complete cycle’s length from the point of entrance of cycle is C
And also note that as the hare is going to cycle many times before it finally meets tortoise in the first phase we should hence assign it as n similarly for tortoise we assign r.
We assign n as the number of cycles that hare takes around to intersect and r is for tortoise.
Note that at intersection we observe hare and tortoise are at the same position but we know that hare may need to keep rolling through the cycle before meeting tortoise, similarly for tortoise.
So the distance travelled by hare can be expressed as = F + n(C) + k And the distance travelled by tortoise is = F + r(C) + k
Substituting the above data in Eqn.1
2 x [ F + r(C) + k] = F + n(C) + k
[2 x F] + [2 x r(C)] + [2 x K] = F + n(C) + k
2F - F + 2k - k = nC - 2rC
F + k = ( n - 2r ) * C
As n and r are always going to be integers.
F + k = an_integer x C <--- Eqn.2
This derivation implies that anything that travels a distance of F + k is at the entrance of the cycle.
For Phase 2:
Both hare and tortoise start moving at the same speed(one unit at a time). Note that, tortoise restarts, while hare stays at the same position(k) from the entrance of cycle.
Let the tortoise move F distance from the beginning to reach the entrance of cycle, so consequentially hare also moves F distance as they are both tarvelling at the same speed in the second phase.
Distances travelled in the second phase: Distance travelled by the hare = F Distance travelled by the tortoise = F
As the hare had already covered k distance in phase 1 and then it covers the F distance to cover a total distance of F+k from the entrance of cycle.
And as we noted/proved while stating Eqn.2 it’s evident that the hare and tortoise meet each other and their point of intersection is the entrance of the cycle.
JavaScript solution to a few questions using this algorithm:
Statement: Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one duplicate number in nums, return this duplicate number.
var findDuplicate = function(nums) {
let hare = nums[0], tortoise = nums[0];
do{
tortoise = nums[tortoise];
hare = nums[nums[hare]];
}while(hare !== tortoise);
tortoise = nums[0];
while(tortoise !== hare){
tortoise = nums[tortoise];
hare = nums[hare];
}
return hare;
};
Statement: Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
var detectCycle = function(head) {
if(!head || !head.next || !head.next.next) return null;
let hare = head, turtle = head;
do{
hare = hare.next.next;
if(!hare.next || !hare.next.next) return null;
turtle = turtle.next;
}while(hare !== turtle);
hare = head;
while(hare !== turtle){
hare = hare.next;
turtle = turtle.next;
}
return hare;
};
What About Big O?
- The time complexity of this algorithm is linear: O(n).
- The space complexity of this algorithm is constant: O(1).
Other articles I'll recommend you to read:
Make sure to share this if you found it helpful, and keep learning, you're a genius.