Algorithm Spotlight: Floyd’s Cycle Detection Algorithm
Last Updated: March 8, 2021
Welcome to the second week of Algorithm Spotlight! This week our featured algorithm is…drum roll please…Floyd’s Cycle Detection Algorithm!
Right before we begin, if you missed out on the previous episode, here’s the Euclidean Algorithm article:
Algorithm Spotlight: Euclidean Algorithm
Learn how the Euclidean Algorithm works in this week’s Algorithm Spotlight!
The Problem Statement
Linked List Cycle - LeetCode
Given a linked list, determine if it has a cycle in it. To represent a cycle in the given linked list, we use an…
Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer
pos which represents the position (0-indexed) in the linked list where the tail connects to. If
pos == -1, then there is no cycle in the linked list.
Want to read this story later? Save it in Journal.
Input: head = [3,2,0,-4], pos = 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.
Idea 1: Use a Set
The naive way of solving a cycle detection problem like this can be solved easily with a set:
Idea 2: Floyd’s Cycle Detection Algorithm
The first approach was a great idea, except it isn’t very smart. Let’s try to improve the code with Floyd’s Cycle Detection Algorithm.
The idea behind Floyd’s Cycle Detection Algorithm is where there are two pointers - a fast pointer (“hare”) and a slow pointer (“tortoise”). The slow pointer moves one step at a time, while the fast pointer moves two steps. Both pointers will move around the (possibly cyclic) list. If the list is not cyclic, both pointers will never contain the same data. If the list is cyclic, sooner or later, both pointers will meet. (see below for proof)
Now let’s prove that Floyd’s Cycle Detection Algorithm works mathematically. We can set the distance from the beginning to the start of the cycle to be x, the distance from the start of the cycle to the first place where the fast and slow pointer meets y, and the distance from y to the start of the cycle z.
Now we have our variables, we can define how many steps the fast and slow pointer moves:
fast pointer: x + 2y + z
slow pointer: x + y + z
Want to see the proof that the two pointers will meet? Check it out: https://math.stackexchange.com/questions/913499/proof-of-floyd-cycle-chasing-tortoise-and-hare/913529#913529.
Now that you have a solid understanding of Floyd’s Cycle Detection Algorithm, let’s implement it!
Implementing Floyd’s Cycle Detection Algorithm
Great work! Now onto some fun practice problems!
As always, practice makes perfect, so here are some sample problems for you to practice. Good luck!
Linked List Cycle II - LeetCode
Given a linked list, return the node where the cycle begins. If there is no cycle, return null. To represent a cycle in…
- We can break this problem down into two steps:
- Finding if there is a cycle in the linked list
- If there is a cycle, find the node where the cycle begins
Find the Duplicate Number - LeetCode
Given an array nums containing + 1 integers where each integer is between 1 and n (inclusive), prove that at least one…
- The idea here is the same as Linked List II, except for this is an array, not a linked list.
Happy Number - LeetCode
Write an algorithm to determine if a number n is "happy". A happy number is a number defined by the following process…
- At each step, perform the operation described, then check if the operations performed so far is a cycle.