We are onto our second pattern for LeetCode style interviews this week: the fast and slow pointer patter. Although technically still a two pointer pattern, there’s a specific style to this where one variable moves at a certain speed – perhaps one element at a time – and the other variable moves two at a time. This style is famously useful for detecting cycles within linked lists and arrays. But we will try to see if there are other types of problems where this is useful as well!

Problem #20 – LinkedList Cycle

Let us have a basic intro to what a linked list is because we haven’t covered it so far. A linked list is a data structure with two items: a pointer to the next ‘node’ and the value of the current ‘node’. What exactly is a node? This is fancy language which means an instance of the linked list class. You can implement a Node class as well as a LinkedList class, which will initialize and join a bunch of nodes. This is how programming languages that already have a LinkedList data structure implement them under the hood. Given how LinkedLists are known to operate, several things need to stand out to you.

1. A LinkedList element cannot be indexed into like an array
2. To find an element is always an O(N) operation in a LinkedList. No way around it.
3. The end of the LinkedList is signified by a node whose next node is null (or None in Python)

In such a structure, you can imagine, trying to find a cycle becomes problematic. By definition, we will be stuck in an infinite loop as there is no pointer which points to None. The immediate solution that may occur to you is to use an additional data structure to store the pointer value of every node we encounter. It is important to store the pointer itself and not the value because a linked list can theoretically have several same values.

While this solves the issue, it is common for problems like these to specify an additional constraint on the memory. How would you solve the problem if you cannot use another data structure like an array or a hash table to track nodes we have already visited? The solution: fast and slow pointer pattern.

If you use this technique, you’ll be able to find a cycle within a loop easily, and it is mathematically guaranteed. A cycle exists in the LinkedList if both pointers meet at any point. Let us prove this for two linked lists of odd and even length. [1, 2, 3, 4] and [1, 2, 3, 4, 5]. Case one will be labelled in orange and case two will be green.

1, 1 and 1, 1

2, 3 and 2, 3

3, 1 and 3, 5

4,3 and 4,2

1, 1 and 5, 4

1, 1 and 1, 1

Convergence!

Problem #21 – Middle of the LinkedList

It’s simple what the problem is asking. One point to keep in mind is that in lists of even length, we need to return the second middle element. In odd lists there is only one element, so there’s no problem!

This problem is simple to solve with the fast and slow pattern. Simply begin iterating one at a time with one pointer and two at a pointer with another. By the time the second pointer has reached the end of the list, the first pointer will be rooted at the middle, since it moved half as fast as the second pointer. This is true for either the odd case or the even case. The slow pointer will always reach the second middle element by the time the fast pointer is done traversing the list.

Problem #22 – Start of LinkedList Cycle

Now, we are not just trying to determine if there is a cycle or not. We want to know the starting point of the cycle, which will be the point where the last element points back to an earlier element in the list.

This is a really tricky problem, and I fail to imagine how anyone who has never solved this problem will be able to figure anything out in an interview. Maybe I am not an engineer pro max, which sucks for me. But I had to Google this problem’s trick. If you can find the length of the cycle within the linked list, you can increment a pointer by that amount. Now you can start moving two pointers one by one, and they should meet at the starting point of the LinkedList.

You can mathematically prove it once you have this idea, however. The length of the cycle is C and there are k nodes until the cycle begins. We advance the fast pointer by C nodes to begin, and then both pointers begin moving forward. By the time the slow pointer moves ahead k nodes, it enters the LinkedList’s cycle. Meanwhile, the fast pointer will be at C + k nodes. This will place the fast pointer at the beginning of the cycle two and both of them will intersect!

These problems are all going to be O(N) complexity.

Problem #23 – Happy Number

A happy number is a number that sums to one when it’s squares are added together repeatedly. In the case that the number isn’t happy, there will be an infinite loop, which needs to be handled.

The easy solution is to use a dictionary to keep track of what numbers we have encountered in each iteration. The moment we run into a number we’ve seen already, that is a cycle, so the number isn’t happy. A clean way to find the squares of each digit is to iterate backwards from the number, which can be done by repeatedly taking its modulus and dividing it by 10.

This solution adds a dictionary to the solution which takes space, but it doesn’t add O(N) to the space complexity of the problem. The complexities of this problem will be discussed later, but first let’s talk about the fast and slow pointer solution to the problem. This problem seems similar to finding a cycle in a linked list, doesn’t it? How would we use that pattern here?

We will declare two variables, slow and fast, and we will pass them through a helper function that we’ll design, which squares and sums the digits. The slow variable will go through the function once and the fast one will go through it twice in rapid succession. There are two cases: the number is a happy number or it isn’t. In the former case, both the slow and fast pointers will converge to 1 eventually. The square of 1 will always remain 1, so both numbers will become equal. OR the second case, where there’ll be a cycle between a series of numbers and the fast/slow pointers will converge once again, as has been proved in Problem #20. Either way, we will exit our loop when both variables are equal to each other, and if they’re equal to 1, that is a happy number; otherwise, not.

Now, what’s the time and space complexity of these solutions? It’s not that trivial to think about that. All unhappy numbers get stuck in a cycle, whose length can be arbitrary. Turns out, all unhappy numbers within 1000 will reach a cycle within 1001 steps. Also, the number of digits in the number is log(number) in base 10. After a series of confusing mathematical equations, we can derive that the time complexity of this solution will be O(log N) and the space complexity will be reduced to O(1), even though the first solution would have a space complexity of O(243) or O(1). This solution is cleaner and more efficient all the same.

Problem #24 – Palindrome LinkedList

We have a problem to determine if a LinkedList is a palindrome or not. This is tricky because we cannot traverse a LinkedList backwards, and we lean towards not using more space – which would make the problem trivial. Always keep this in mind, even if the problem doesn’t explicitly state (which in this case, it does). How can we do this cleanly while using the fast/slow pointer technique?

We can find the mid point of the LinkedList how we did in Problem #21. Now that we have that, we can start reversing the first half of the list¹. We need to be careful of what variables we use to iterate and keep the right copies of the head to each list here. Now, we are able to compare the original first half of the list and the reversed second half easily. Return False the moment we find an inequality, otherwise keep continuing and eventually return True.

Problem #25 – Rearrange a LinkedList

Given a LinkedList, we want to reverse the second half and rearrange our original list in an alternative order with the reversed half.

The solution to this problem will build upon everything we have learnt so far and then some. Think: what would you never to do here? First, we need to find the mid point of our LinkedList. Fair enough. We use the fast and slow algorithm to do that. Now, we can begin reversing the list starting from the slow pointer. By the end, the variable which points to the previous node will contain the head of the reversed LinkedList.

Now comes the tricky bit for this problem. We have the head of the entire LinkedList and the reversed LinkedList. We need to alternative between the two and join them together. This can be done by looping until the end of our reversed list while:

1. we point the first half’s next to the second half
2. and then we point the second half’s next to the first half
3. and we advance both lists forward by keeping a temporary variable that tracks the next node in the lists

Problem #26 – Cycle in a Circular Array

What on earth is a circular array?! While moving forward, if the end of an array is reached, we jump back to the first element. While moving backwards, if the beginning of an array is reached, we jump to front to the last element and continue moving. We move front or back depending on the value of the element. Positive means forward, negative means backwards. There are two additional restrictions in this problem. The cycle must have at least one element and the cycle must only move in one direction. What can we do?

In problems such as these, the modulus operator comes in handy because we want to ensure that we don’t cross the boundaries of our array. Yet, we still want to continue moving, which is exactly what a modulus allows us. Let’s say traversing forward an element takes us to value 7. If we mod it with the length of our array – let’s say 5 – we will get the value 2, which is essentially continuing the value from the front. The same is true for negative indices. If the index is -3, the mod value will be 2, which is essentially the same as traversing 3 units from the back i.e. the second element of the array.

There is an additional trick to this problem, which is detecting when a cycle doesn’t exit. We need to keep track of what direction we’re moving in from the start. The moment we find a direction change, we can exit from the function by returning False. Furthermore, this may not be apparent, but the problem will be at the very least O(N^2) because we will need to determine if a cycle exists from every element as a starting point. It may be the case that element 0 doesn’t lead to a cycle, but element 3 might! This is important for this problem.

This is a really tricky problem, so don’t be dejected if you don’t get it the first time. I still have difficulties with this after multiple attempts.

1. Which is a classic, interesting problem in itself that I recommend you to solve. It drills the basics of LinkedLists in your head in a way that other problems can’t seem to, in my opinion ↩︎