Cycle Detection is a coding challenge with medium difficulty in the HackerRank data structures category. In this blog post, we’ll discuss how we can solve it in JavaScript in O(n) time and O(1) space complexity.
Problem Statement
A linked list is said to contain a cycle if any node is visited more than once while traversing the list. Given a pointer to the head of a linked list, determine if it contains a cycle. If it does, return 1. Otherwise, return 0.
Read full details and access the challenge on Cycle Detection | HackerRank
Note
Before we dive into the solution, I want to add that there’s a bug if you solve this challenge in JavaScript. Seem like the creator of the challenge initiates a ‘temp’ as a constant instead of a variable. This causes us unable to submit our code as it would cause a runtime error.
So, if you just want to learn, you can practice making your solution and comparing it to my solution below as a reference.
But if you want to submit it, I suggest rewriting your code in another language. I’ve found others saying they have errors in JavaScript but none have said so in other languages.
And another note, this challenge doesn’t provide the hasCycle function which is a placeholder for your solution, so you have to make it yourself.
Intuitive Solution
function hasCycle(head) {
let set = new Set();
while (head) {
if (set.has(head)) {
return 1;
} else {
set.add(head)
};
head = head.next;
}
return 0;
}Time Complexity : O(n)
Space Complexity : O(n)
If we understand the challenge correctly, we’re basically checking if any node is visited twice.
So, we make a set which functions as a history to check if a certain node has been visited before.
Then, we iterate though the nodes (or head in this case) and check if that node has been visited before by checking if it is contained in the set. If it has been visited before, then we return 1, but if it hasn’t, we add the node to the set and continue the iteration to the end of the linked list.
If we reach the end of the linked list, that means it does not contain a cycle and we return 0.
We’re iterating through the linked list once so we have O(n) time and since we use a set to contain the visited nodes, we have O(n) space complexity.
We can further optimize this code into O(1) space with the solution below.
Optimized Solution – Floyd’s Cycle Finding Algorithm
function hasCycle(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return 1;
}
return 0;
}Time Complexity : O(n)
Space Complexity : O(1)
Floyd’s Cycle Finding Algorithm or Floyd’s Tortoise and Hare Algorithm is an algorithm that is used to detect a loop or a cycle in a linked list.
First, we use two pointers, namely slow and fast. Slow moves one node at a time but fast moves through two nodes at a time.
They’ll keep moving until either fast reaches the end of the linked list (null) or slow and fast meets.
If the linked list does not contain a cycle, fast will reach the end. But, if the linked list contains a cycle, fast will keep moving since there’s no end to the linked list and will eventually stop when it meets with slow signaling that there’s a cycle.
If fast reaches the end, we return 0 and if fast meets slow, we return 1.
We are iterating through the linked list once, so we still have O(n) time. But, we don’t use any extra variables like arrays or sets, so we have O(1) time complexity which is an improvement compared to the solution above.
Conclusion
That’s how you can solve and optimize the Cycle Detection Challenge in HackerRank.
If you have an approach different from mine, please do comment below!
Check out the rest of my blog for more helpful contents on Data Structures and Algorithms in JavaScript! We’ll also discuss more HackerRank solutions using JavaScript in this blog!
See you next post!