Image credits to Ella Wei at Pexels

Floyd’s Tortoise and Hare Algorithm — for beginners

I’ve been brushing up on my algorithms by focusing on Leetcode Medium problems — or trying to, at least. I came across the Find the Duplicate Number question and learned about the Floyd’s Tortoise and Hare solution. It was a bit challenging to grasp, but with the help of some very useful art and re-reading the code, I decided to share how and why this particular algorithm is so helpful (and time efficient!)

First approach

My first thought was to iterate through this array, and use the JavaScript method . returns the index of the element if it can be found. I thought if I could iterate through the array and does not return -1, it would mean the number is not unique and therefore return nums[i].

Spoiler alert: I did say this was my first approach! This approach did not work, and that’s because it returned the value at the nums array at the zeroth index. Since nums at the initial index (which is 0) is 1, it is technically true that it is not equal to -1, and so this code would return the first value that this is true.

Proof that my initial approach doesn’t work!

Second approach

I took a second look at the constraints: we can’t modify the array and should be using constant O(1) time. Finally, I gave in and checked the solutions. To my surprise, I saw a number of solutions use something called Floyd’s Tortoise and Hare Algorithm.

Even after taking a look at their solution and watching a YouTube walkthrough, I didn’t understand how this approach was optimal. That’s when I came across Alisa Bajramovic’s blog post on Dev. I found it helpful, especially the diagram, but when I went back to my code, I was still confused.

The Basics

We start by instantiating two variables, and . is assigned the value of the nums array at index 0, and is assigned the value of nums at tort, which is one ahead, so at index 1. While the value of does not equal the value of , is the value of the next element (which is where hare was previously), and is the value of nums at the third element, or rather two indices ahead.

is then the value of 0.

While is not equal to , is assigned the value of nums at the tort index, and then is assigned the value of nums at the index.

At the end of the while loop, you’ll return the variable .

Using this algorithm, we begin with assigned the value of 1, and to the value of 3. Since 1 !== 3, is now the value of 3, and has the updated value of 2 since it is at index 3. Again, these are not equal. You’ll continue to go through the array until reaches the end of the array — and since is the same value at , we return , or the value of 2.

Runtime

This algorithm has a runtime of O(N), with the main factor that impacts runtime being the length of the array.

I’ve focused on building lately, and the focus on algorithms has been a great change of pace. These algorithms challenged me to consider different ways to achieve the solution — and it’s been even more challenging to find the optimal one! I’ve linked Alisa’s blog below, as I found the explanation and diagram helpful.