The Fast & Slow pointer approach, also known as the Hare & Tortoise algorithm, is a pointer algorithm that uses two pointers which move through the array (or sequence/LinkedList) at different speeds. This approach is quite useful when dealing with cyclic LinkedLists or arrays.
By moving at different speeds (say, in a cyclic LinkedList), the algorithm proves that the two pointers are bound to meet. The fast pointer should catch the slow pointer once both the pointers are in a cyclic loop.
One of the famous problems solved using this technique was Finding a cycle in a LinkedList.
Example 1:
1 -> 2 -> 3 -> 4 -> 5 -> 6
|_ _ _ _ _ _ _ |
there's a cycle from 6 -> 3
Example 2:
2 -> 4 -> 6 -> 8 -> 10 -> null
there's no cycle
Implementation: LinkedListCycle
The logic is to have two pointers: one slow and one fast. Two situations can arise: 1. If there's no cycle, the fast pointer reaches the end of the list. 2. If there's a cycle, the fast pointer catches up with the slow pointer.
O(n), since the fast pointer will travel n nodes.
O(1), we are not storing anything.
1 -> 2 -> 3 -> 4 -> 5 -> 6
|_ _ _ _ _ _ _ |
Length of cycle is 4 (3 -> 6)
Implementation: LengthOfCycle
We find a meeting point of the slow and fast pointers using the method above. Once we do, we start a third pointer and keep iterating till the slow and third pointers meet again.
The logic is:
Regardless of where the third and slow pointer meets, its will always have travelled the full loop, as shown in the diagram above.
O(n)
O(1)
1 -> 2 -> 3 -> 4 -> 5 -> 6
|_ _ _ _ _ _ _ |
start is 3.
Implementation: LinkedListStart
The algorithm is: we find the length of the cycle. We substract that from the total length and the difference must be the index where the cycle starts. However, there's an issue with this approach. To find the total length, we will have to use O(n) space, which we don't want to.
Instead, we: 1. Find the cycle length. 2. Take two pointers, say: ptr1 and ptr2. 3. Move ptr2 by the length of the cycle. 4. Keep moving both till they meet. 5. The meeting point is the start of the cycle.
O(n)
O(1)
Example 1:
Input: 23
Output: true (23 is a happy number)
Explanations: Here are the steps to find out that 23 is a happy number:
2^2 + 3^2 = 13
1^2 + 3^2 = 10
1^2 + o^2 = 1
Example 2:
Input: 12
Output: false (12 is not a happy number)
Explanations: Here are the steps to find out that 12 is not a happy number:
12+221^2 + 2 ^212+22 = 1 + 4 = 5
525^252 = 25
22+522^2 + 5^222+52 = 4 + 25 = 29
22+922^2 + 9^222+92 = 4 + 81 = 85
82+528^2 + 5^282+52 = 64 + 25 = 89
82+928^2 + 9^282+92 = 64 + 81 = 145
12+42+521^2 + 4^2 + 5^212+42+52 = 1 + 16 + 25 = 42
42+224^2 + 2^242+22 = 16 + 4 = 20
22+022^2 + 0^222+02 = 4 + 0 = 4
424^242 = 16
12+621^2 + 6^212+62 = 1 + 36 = 37
32+723^2 + 7^232+72 = 9 + 49 = 58
52+825^2 + 8^252+82 = 25 + 64 = 89
Step ‘13’ leads us back to step ‘5’ as the number becomes equal to ‘89’, this means that we can never reach ‘1’, therefore, ‘12’ is not a happy number.
With squaring and adding, it always goes into a cycle. However, if its a happy number, the cycle loops with 1, else it returns to the starting number and loops again.
Our logic is to detect the cycle and then check what number it loops with. If its a happy number, it will loop with 1, else it will loop with some other number.
O(logn)
O(1)
Example 1:
Input: 1 -> 2 -> 3 -> 4 -> 5 -> null
Output: 3
Example 2:
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
Output: 4
Example 3:
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null
Output: 4
Implementation: LinkedListMiddle
For odd case,
1 -> 2 -> 3 -> 4 -> 5 -> null
there are 5 nodes in the list. 5/2 = 2. With 0-based index, that's node 3, which is the correct answer.
For even case,
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
there are 6 nodes in the list. 6/2 = 3. With 0-based index, that's node 4, which is the correct answer.
So, we need to calculate the total length of the list. Then divide by 2, which will give us the mid index. On a second pass, we can simply find that index and return.
O(n)
O(1)