Fast and slow pointers

Author

Pham Nguyen Hung

Published

July 21, 2023

Fast and slow pointers

Definitions

This is not a data structure, but a pattern of coding interview questions. This is something passed down from languages with pointers such as C++ or Java. The idea is that I will traverse the array with two pointers simultaneously, one of them will be “faster” than the other, in the sense of headstart (start at a further location while moving at the same speed) or speed (the fast one move faster e.g., two steps at a time, while the slow one will move one step at a time while starting at the same locaiton). This pattern is very useful for solving problems related to linked lists or arrays. Also known as the Floyd’s “Hare and Tortoise Algorithm”.

Problem

1. Happy Number

Intuition

The hint lies at the problem statement: it is either going to 1, or going into a loop. If there is a loop, fast and slow pointers should be used.

Algorithm

  1. Initialize the two pointers slow and fast to n and the helper function to calculate sum of square of digits (\(SS\)).
  2. At each step, assign slow to the \(SS\) of itself and fast to the \(SS\) of \(SS\) of itself. I check and then return accordingly when I go into loop or encounter 1.

Complexity

  • Time complexity: \(O(\log n)\): The detailed analysis can be found here. The first solution with HashSet is helpful as it explains how can I rule out the third possibility that is not mentioned in the problem statement: the number increases infinitely. Simply, it will all goes down below 243. The \(\log\) appears here because it is the cost of processing every unit of a number. The full term is \(O(243 \times 3 + \log n+\log \log n+\log \log \log n)... = O(\log n)\) but the \(\log\) term dominates the sum. For our two pointers, the cost is \(O(\log n)\) for each, but \(2\) is a constant so omitted.

  • Space complexity: \(O(1)\): I only need to store pointers.

Code

class Solution:
    def isHappy(self, n: int) -> bool:
        if n == 1:
            return True
        slow = fast = n 
        
        while True:
            slow = self._sumOfSquare(slow)
            fast = self._sumOfSquare(self._sumOfSquare(fast))
            if slow == 1 or fast == 1:
                return True
            if slow == fast:
                return False

    def _sumOfSquare(self, n: int) -> int:
        result = 0
        while n != 0:
            result += (n % 10)**2
            n //= 10
        return result

2. Linked List Cycle

The introductory fast and slow pointers problem. If there is a loop, the fast and slow pointers are bound to meet with each other somewhere.

Intuition

If I am not told about the problem, I don’t think I can come up with the solution. This is something you have to know beforehand. But well, in an interview, you will be assessed on your ability to solve harder problems with this approach, so that is our real goal.

Algorithm

  1. Initialize the two pointers fast and slow to head.
  2. At each step, assign fast to the next of the next of itself and slow to the next of itself. I check and then return accordingly when I go into loop i.e., the two pointers meet.
  3. If I reach the end of the list, I return False.

Complexity

  • Time complexity: \(O(n)\): Both pointers traverse the list at least once.

  • Space complexity: \(O(1)\): I only need to store pointers.

Code

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # Easy case
        if head is None or head.next is None:
            return False
        
        # General case
        fast = slow = head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False

3. Remove Nth Node From End of List

The idea is to initialize two fast and slow pointers, but started at different positions while moving at the same speed. I want that when the fast pointer hits the end, the slow pointer is at the node before the to-be-removed node to rearrange the connection.

Intuition

This is the second type of fast and slow pointers: they move at the same speed but start at different positions. The idea is that I want the fast pointer to hit the end of the list, while the slow pointer is at the node before the to-be-removed node. Then I can rearrange the connection.

Algorithm

  1. Initialize the two pointers fast and slow to head.
  2. Move the fast pointer n+1 steps ahead of the slow pointer.
  3. Move both pointers until the fast pointer hits the end of the list.
  4. Remove the node next of the slow pointer.

Complexity

  • Time complexity: \(O(n)\): Both pointers traverse the list at most once.

  • Space complexity: \(O(1)\): I only need to store pointers.

Code

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # Easy case
        if head.next is None:
            return
        
        # General case
        # Fast and slow pointer
        slow = fast = head
        for _ in range(n+1):
            if fast:
                fast = fast.next
            else:
            # If fast pointer is already None before the end, there is just one
            # case and it is the head needs removing, so I return the next element
                return head.next
        # If not, I start to move the slow and fast pointers to the end.
        while fast:
            slow, fast = slow.next, fast.next
        
        slow.next = slow.next.next
        
        return head

4. Middle of the Linked List

Intuition

Because the fast pointer is doubly faster than the slow, when the fast pointer hits the end, the slow pointer will be at the middle node.

Algorithm

  1. Initialize the two pointers fast and slow to head.
  2. Move the fast pointer 2 steps and the slow pointer 1 step at each iteration till termination.
  3. Return the slow pointer or the node next to it.

Complexity

  • Time complexity: \(O(n)\): Both pointers traverse the list at most once.

  • Space complexity: \(O(1)\): I only need to store pointers.

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head.next is None:
            return head
        slow, fast = head, head
        while fast.next is not None and fast.next.next is not None:
            slow = slow.next
            fast = fast.next.next
        if fast.next is not None:
            slow = slow.next
        return slow

5. Circular Array Loop

Intuition

Let’s ignore the instruction to solve in \(O(n)\) time complexity for now (\(O(1)\) space complexity is achieved with pointers).

For every element, I need to check if it is a part of a cycle. If it is, I need to check if the cycle is valid. If it is, I return True. Otherwise, I continue to check the next element. A cycle is invalid if there exist elements with different signs in the cycle. This means that at least one product between a pair of elements is negative. The direction direction condition can be tracked with a variable, and the terminating condition can be signaled by setting the pointer to \(-1\). A cycle also needs to have more than one element. This means that an element with value divisible by the length of the array is invalid. This solution is \(O(n^2)\) time complexity, as I will have a nested loop each iterating through the array in the worst case.

To move on to the \(O(n)\) solution, I can keep track of the elements I have visited. The most straightforward is having an array or a HashMap, but it violates the \(O(1)\) space complexity. Hence, this means modifying the array in place into 0.

Algorithm

  1. Initialize the variable current_direction to None.
  2. Iterate through the array. If the element is divisible by the length of the array, continue to the next element.
  3. If the element is not divisible by the length of the array, set the current_direction to True if the element is positive, and False if the element is negative. Set the slow and fast pointers to the current index.
  4. While the two pointers have not met or terminating condition (pointer is \(-1\)), move the slow pointer one step and the fast pointer two steps, each time checking for the terminating condition. If the pointers are equal and both are not \(-1\), return True.
  5. Return False at the end.

Complexity

  • Time complexity: \(O(n^2)\) or \(O(n)\): Depend on the implementation and condition whether I can modify the array in place.

  • Space complexity: \(O(1)\): I only need to store pointers.

Code

class Solution:
    def circularArrayLoop(self, nums: List[int]) -> bool:
        current_direction = None
        for i in range(len(nums)):
            if not nums[i] % len(nums):
                continue
            current_direction = True if nums[i] > 0 else False
            slow = fast = i
            while slow != fast or slow != -1 or fast != -1:
                slow = self._one_step(nums, slow, current_direction)
                if slow == -1:
                    break
                fast = self._one_step(nums, fast, current_direction)
                if fast != -1:
                    fast = self._one_step(nums, fast, current_direction)
                
                if fast == -1 or slow == fast:
                    break
                
            if slow == fast and slow != -1:
                return True
        
        return False

    def _one_step(self, nums, current_index, current_direction):
        next_direction = True if nums[current_index] > 0 else False
        if ((next_direction != current_direction) or 
            (not nums[current_index] % len(nums))):
            return -1
        next_step = (current_index + nums[current_index]) % len(nums)
        return next_step

Optimized \(O(n)\) version:

class Solution:
    def circularArrayLoop(self, nums: List[int]) -> bool:
        if len(nums) < 2:
            return False
        n = len(nums)
        for i in range(n):
            if nums[i] == 0:
                continue
            
            slow, fast = i, (i + nums[i]) % n
            while nums[i] * nums[fast] > 0 and nums[i] * nums[(fast + nums[fast])%n] > 0:
                if slow == fast:
                    if slow == (slow + nums[slow])%n:
                        break
                    return True
                slow = (slow + nums[slow])%n
                fast = (fast + nums[fast])%n
                fast = (fast + nums[fast])%n

            slow = i
            sgn = nums[i]
            while sgn * nums[slow] > 0:
                tmp = (slow + nums[slow])%n
                nums[slow] = 0
                slow = tmp
        return False

6. Find the Duplicate Number

Intuition

Dirichlet’s principle will help you to prove that there must be a duplicate in the array. Next, because of the constraints of numbers from \(1\) to \(n\) inside an array of length \(n+1\), I can see that I can access every element of the array with the function nums[index]. This means that the array can be turned into a linked list, where the value is the index and the next pointer is the value of the element. In this linked list, the duplicate element creates a cycle, as there are at least two elements pointing to it, making it the entrance of a cycle.

However, the problem is not Is there a cycle? but Where is the cycle?. In other words, I need to find the entrance to the cycle. This bears similarity to Linked List Cycle II. The solution is to use fast and slow pointers as before, with some insights from math to find the entrance.

I define the following variables (see diagram above): - \(F\): the distance from the start of the array to the entrance of the cycle - \(a\): the distance from the entrance of the cycle to the meeting point of the fast and slow pointers - \(C\): the length of the cycle

At the intersection point i.e., where two pointers meet, I have the following equations: \[2 \times \text{distance slow pointer moves} = \text{distance fast pointer moves}\]

Which is equivalent to: \[ 2(F + a) = F + a + nC, \text{for some n} \in \mathbb{N} \] This gives us an interesting equation: \[ F = (n-1)C + (C - a) \] In plain English, this means that if the two pointers both start at first element, the distance from the intersection point found to the cycle entrance is equal to the distance from that first element to the cycle entrance. This means that if I move one pointer back to the first element and move both pointers one step at a time, they will meet at the cycle entrance.

Algorithm

  1. Set the fast and slow pointers to the first element of the array.
  2. Move the fast pointer two steps and the slow pointer one step at a time, until they meet.
  3. Set the slow pointer to the first element of the array.
  4. Move both pointers one step at a time, until they meet.
  5. Return the meeting point.

Complexity

  • Time complexity: \(O(n)\): I need to traverse the array a number of time.
  • Space complexity: \(O(1)\): I only need to store pointers.

Code

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # Phase 1: Intersection point
        fast = slow = nums[0]
        while True:
            fast = nums[nums[fast]]
            slow = nums[slow]
            if fast == slow:
                break
        
        # Phase 2: Find the cycle entrance
        slow = nums[0]
        while slow != fast:
            fast = nums[fast]
            slow = nums[slow]
        
        return slow

7. Palindrome Linked List

Intuition

Obviously, the first way is to copy the linked list over to an array, and then use two pointers to check for palindrome. However, to satisfy the \(O(1)\) space complexity, I need to check for palindrome in place. The intuition is if a linked list is a palindrome, the second half reversed will be the same as the first half. I can use two pointers to find the middle of the linked list, and then reverse the second half. Finally, I can compare the first half and the second half to check for palindrome. Of course, this will modify the linked list in place, so I need to restore the second half if the linked list is involved in another problem.

Algorithm

  1. Use two pointers to find the middle of the linked list.
  2. Reverse the second half of the linked list.
  3. Compare the first half and the second half to check for palindrome.
  4. Reverse the second half again to restore the linked list.
  5. Return the result.

Complexity

  • Time complexity: \(O(n)\): I need to traverse the linked list a number of time.

  • Space complexity: \(O(1)\): I only need to store pointers.

Code

from typing import Optional
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if not head.next:
            return True
        # Iterate the linked list to find the middle
        # This part can be turned into a separate method
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        # Reverse the second half
        second_half_head = self._reverseLinkedList(slow.next)
        first_half_current, second_half_current = head, second_half_head

        # Compare the first half and the second half
        while second_half_current:
            if second_half_current.val != first_half_current.val:
                return False
            second_half_current, first_half_current = second_half_current.next, first_half_current.next
        
        # Restore the linked list
        slow.next = self._reverseLinkedList(second_half_head)
        return True

    def _reverseLinkedList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre, cur, nxt = None, head, head.next
        while nxt:
            cur.next = pre
            pre = cur
            cur = nxt
            nxt = nxt.next
        cur.next = pre
        return cur