Using fast and slow pointers at once

Table of Contents

How to manipulate multiple variables or pointers at once
Floyd’s tortoise and hare algorithm or Floyd’s Cycle Detection algorithm
Reading material
TODO

How to manipulate multiple variables or pointers at once

e.g. using two pointers for a string

e.g. using two pointers to traverse a linked list and each of them are going at different speeds from one another.

e.g. longest palindromic substring in a string. for every letter, start two pointers going in the opposite directions.

Floyd’s tortoise and hare algorithm or Floyd’s Cycle Detection algorithm

https://en.wikipedia.org/wiki/Cycle_detection

The fast and slow pointers algorithm, also known as Floyd’s Cycle Detection Algorithm or the “tortoise and hare” algorithm, is a clever technique that uses two pointers to traverse a data structure at different speeds. This approach is particularly effective for problems involving linked lists and cyclic data structures.

Floyd’s Cycle Detection Algorithm, also known as the “tortoise and hare” algorithm, is a pointer-based technique used to detect cycles in a sequence, such as a linked list or a function’s iteration path. It uses two pointers moving at different speeds to identify a cycle and can also determine the cycle’s starting point and length.

Floyd’s Cycle Detection Algorithm is versatile and widely used due to its efficiency and simplicity, making it a fundamental tool in computer science and related fields.

The fast and slow pointer technique is a cornerstone of efficient algorithm design, especially for problems requiring minimal space complexity.

How it works

The algorithm initializes two pointers, traditionally called “slow” and “fast”, at the beginning of the data structure (e.g., the head of a linked list). In each iteration:

The slow pointer moves one step forward.
The fast pointer moves two steps forward.

Key principle

The core idea is that if there is a cycle in the data structure, the faster pointer will eventually catch up to and meet the slower pointer within that cycle. If there’s no cycle, the fast pointer will reach the end of the data structure first.

Analogy

Think of a race between a tortoise and a hare on a circular track, as described by Medium. The tortoise moves slowly, one step at a time, while the hare is swift, taking two steps at a time. If the track is circular, the hare will eventually lap the tortoise and meet it at some point.

Advantages

Time efficiency: The algorithm typically achieves a time complexity of O(n) for linked lists, avoiding the need for nested loops that could lead to O(n²) complexity.
Space efficiency: It often operates with constant space complexity, O(1), as it only uses a few additional variables for the pointers.
Simplicity: Once the concept is understood, the logic is relatively straightforward to implement.

In essence, the fast and slow pointers technique is a powerful tool for navigating and analyzing linear and cyclic data structures efficiently and with minimal memory usage.

Some common applications of Floyd’s Cycle Detection Algorithm

Determine if a linked list has an even or odd number of nodes
Detecting Cycles in a Linked List
- Problem: Determine if a singly linked list contains a cycle.
- How It Works: Use two pointers: slow (moves one step at a time) and fast (moves two steps at a time). If they meet, a cycle exists; if fast reaches the end (null), there’s no cycle.
- Example: For a linked list 1 -> 2 -> 3 -> 4 -> 2 (cycle at node 2), the pointers meet inside the cycle, confirming its presence.
- Application:
  - Validating linked list integrity in data structures.
  - Debugging linked list implementations to detect loops.
  - Used in problems like LeetCode #141 (Linked List Cycle).
- Complexity: O(n) time, O(1) space.
Finding the Starting Point of a Cycle
- Problem: Identify the node where a cycle begins in a linked list.
- How It Works: After detecting a cycle using Floyd’s Cycle Detection Algorithm (fast and slow pointers), reset the slow pointer to the head and move both pointers one step at a time. Their meeting point is the cycle’s start.
- Example: In 1 -> 2 -> 3 -> 4 -> 2, the algorithm identifies node 2 as the cycle’s entry point.
- Application:
  - Debugging cyclic linked lists.
  - Used in problems like LeetCode #142 (Linked List Cycle II).
- Complexity: O(n) time, O(1) space.
Cycle Detection in Function Iterations
- Use Case: Detect cycles in sequences generated by iterative functions (e.g., f(x) = x^2 mod n).
- How It Works: Treat the sequence as a linked list where each value points to the next (e.g., x_{i+1} = f(x_i)). Apply Floyd’s algorithm to find if the sequence loops.
- Example: In Pollard’s Rho algorithm for integer factorization, it detects cycles in the sequence to find factors.
- Application: Cryptography, number theory (e.g., Pollard’s Rho for factoring large numbers).
Pollard’s Rho Algorithm for Integer Factorization
- Use Case: Factorize large composite numbers efficiently.
- How It Works: Uses Floyd’s algorithm to detect cycles in a pseudo-random sequence generated by a polynomial (e.g., f(x) = x^2 + c mod n). The meeting point helps compute the greatest common divisor (GCD) to find a factor.
- Example: For n = 8051, the algorithm might find a cycle and compute GCD to discover factors like 97 and 83.
- Application: Cryptographic algorithms (e.g., breaking RSA by factoring large numbers).
Cycle Detection in Graphs
- Use Case: Detect cycles in directed or undirected graphs represented as adjacency lists.
- How It Works: Model the graph traversal as a sequence and apply Floyd’s algorithm to detect if a path revisits a node.
- Example: In a graph traversal where edges define a sequence, the algorithm identifies cyclic paths.
- Application: Used in graph algorithms for deadlock detection in resource allocation or analyzing state machines.
Detecting Cycles in Random Number Generators
- Use Case: Verify if a pseudo-random number generator (PRNG) produces a cyclic sequence.
- How It Works: Treat the PRNG’s output as a sequence and apply Floyd’s algorithm to detect repetition.
- Example: Testing if a PRNG like x_{n+1} = (a * x_n + c) mod m loops after a certain period.
- Application: Testing and validating PRNGs in simulations, cryptography, or gaming.
Finding the Length of a Cycle
- Use Case: Determine the length of a cycle in a linked list or sequence.
- How It Works: After detecting a cycle, count the steps for the slow pointer to return to the meeting point while moving one step at a time.
- Example: In a list with a cycle of length 3, the algorithm computes the cycle length after detecting the cycle.
- Application: Useful in analyzing periodic behaviors in algorithms or data structures.
Detecting Duplicates in Arrays (Related Problem)
- Use Case: Solve problems like finding a duplicate number in an array (e.g., LeetCode #287) where the array can be treated as a linked list.
- How It Works: Treat array indices as pointers (e.g., index -> arr[index]). A duplicate creates a cycle, and Floyd’s algorithm finds the duplicate (cycle’s start).
- Example: For array [1, 3, 4, 2, 2], the algorithm detects 2 as the duplicate by finding the cycle’s entry.
- Application: Efficiently solving array-based problems with constraints like O(1) space complexity.
Finding the Middle of a Linked List
- Problem: Locate the middle node of a singly linked list.
- How It Works: The slow pointer moves one step, and the fast pointer moves two steps. When fast reaches the end (or null), slow is at the middle.
- Example: For 1 -> 2 -> 3 -> 4 -> 5, slow ends at 3 (middle node).
- Application:
  - Splitting a linked list into two halves (e.g., for merge sort).
  - Finding the median in a sorted linked list.
  - Used in problems like LeetCode #876 (Middle of the Linked List).
- Complexity: O(n) time, O(1) space.
Finding the nth Node from the End of a Linked List
- Problem: Return the node that is n positions from the end of a linked list.
- How It Works: Initialize both slow and fast pointers at the head. Move fast forward by n steps, then move both pointers one step at a time until fast reaches the end. The slow pointer will be at the nth node from the end.
- Example: For 1 -> 2 -> 3 -> 4 -> 5 and n = 2, slow ends at 4 (second node from the end).
- Application:
  - Deleting the nth node from the end (e.g., LeetCode #19).
  - Finding specific positions in linked lists for algorithmic problems.
- Complexity: O(n) time, O(1) space.
Detecting Duplicates in an Array (Cycle in Array)
- Problem: Find a duplicate number in an array where values act as indices (e.g., LeetCode #287).
- How It Works: Treat the array as a linked list where each value points to the index it represents (index -> arr[index]). A duplicate creates a cycle, and the fast-slow pointer technique (Floyd’s algorithm) finds the cycle’s entry (the duplicate).
- Example: For array [1, 3, 4, 2, 2], the algorithm detects 2 as the duplicate by finding the cycle’s entry.
- Application:
  - Solving array problems with constraints like O(1) space.
  - Used in problems involving index-value mappings or graph-like structures.
- Complexity: O(n) time, O(1) space.
Checking if a Linked List is a Palindrome
- Problem: Determine if a linked list is a palindrome (reads the same forward and backward).
- How It Works: Use fast and slow pointers to find the middle of the list (slow at middle when fast reaches the end). Reverse the second half of the list starting from slow.next, then compare the first half (from head) with the reversed second half.
- Example: For 1 -> 2 -> 2 -> 1, find middle (2), reverse second half (1 -> 2), and compare to confirm palindrome.
- Application:
  - Validating palindromic structures in linked lists (e.g., LeetCode #234).
  - Used in string or sequence processing with linked list representations.
- Complexity: O(n) time, O(1) space.
Partitioning a Linked List
- Problem: Partition a linked list around a value x so nodes less than x come before nodes greater than or equal to x (as in your previous query).
- How It Works: While not a direct fast-slow pointer application, the technique can be adapted to find a pivot or manage partitions efficiently. For example, fast-slow pointers can help locate a specific node or manage list traversal in related problems.
- Example: For 1 -> 4 -> 3 -> 2 -> 5 -> 2 and x = 3, partition into 1 -> 2 -> 2 -> 4 -> 3 -> 5.
- Application:
  - Rearranging linked lists based on a condition.
  - Used in problems like LeetCode #86 (Partition List).
- Complexity: O(n) time, O(1) space.
Detecting Cycles in Sequences or Iterative Functions
- Problem: Detect cycles in sequences generated by iterative functions (e.g., f(x) = x^2 mod n).
- How It Works: Treat the sequence as a linked list where each value points to the next (x_{i+1} = f(x_i)). Use fast and slow pointers to detect if the sequence loops.
- Example: In Pollard’s Rho algorithm for integer factorization, detect cycles in a sequence to find factors of a number.
- Application:
  - Cryptography (e.g., Pollard’s Rho for factoring large numbers).
  - Analyzing periodic behavior in mathematical sequences or random number generators.
- Complexity: O(n) time, O(1) space.
Happy Number Detection
- Problem: Determine if a number is “happy” (sum of squares of its digits eventually reaches 1, or it loops in a cycle).
- How It Works: Compute the sum of squares of digits iteratively, treating it as a sequence. Use fast and slow pointers to detect a cycle (indicating a non-happy number) or convergence to 1.
- Example: For 19, compute 1^2 + 9^2 = 82, 8^2 + 2^2 = 68, etc. If no cycle is found and it reaches 1, it’s happy.
- Application:
  - Solving problems like LeetCode #202 (Happy Number).
  - Analyzing iterative processes for convergence or cycles.
- Complexity: O(log n) average time, O(1) space.
Reordering a Linked List
- Problem: Reorder a linked list in a specific pattern (e.g., L0 -> Ln -> L1 -> Ln-1 -> ...).
- How It Works: Use fast and slow pointers to find the middle of the list, split it, reverse the second half, and interleave the two halves.
- Example: For 1 -> 2 -> 3 -> 4, reorder to 1 -> 4 -> 2 -> 3.
- Application:
  - Used in problems like LeetCode #143 (Reorder List).
  - Rearranging data structures for specific patterns.
- Complexity: O(n) time, O(1) space.

Key Characteristics of Fast and Slow Pointers

Efficiency: Achieves O(n) time complexity for most applications with O(1) space, making it ideal for in-place operations.
Versatility: Applicable to linked lists, arrays, sequences, and graphs.
Intuition: The difference in pointer speeds allows detection of structural properties (e.g., cycles, midpoints) without extra memory.

Practical Applications Summary

Data Structures: Validating linked lists, detecting corruption, or finding duplicates in arrays.
- Linked Lists: Cycle detection, finding middle, nth node from end, palindrome check, reordering.
- Arrays: Finding duplicates by treating arrays as graphs.
Sequences: Cycle detection in iterative functions (e.g., Pollard’s Rho, happy numbers).
Graph Algorithms: Identifying cycles in state machines, resource allocation, or network analysis.
- Graphs: Detecting cycles in graph-like structures or state machines.
Testing: Ensuring PRNGs or iterative processes don’t produce unintended cycles.
Cryptography: Factoring numbers in algorithms like Pollard’s Rho for breaking encryption.

Complexity analysis of Floyd’s Algorithm

Time Complexity: O(n), where n is the number of nodes or sequence elements.
Space Complexity: O(1), as it uses only two pointers.
Advantages: Simple, efficient, and works in-place without requiring extra memory.
Limitations: Only detects cycles; doesn’t handle cases where cycles are impossible or requires preprocessing for certain applications.

Example

For the linked list example 1 -> 4 -> 3 -> 2 -> 5 -> 2 with a cycle at 2 (from your previous context), Floyd’s algorithm can:

Detect the cycle by having slow and fast pointers meet at some node.
Find the cycle’s start (node 2) by resetting slow to the head and moving both pointers one step at a time.
Compute the cycle length (e.g., if 2 -> 5 -> 2 forms a cycle, length is 2).

Reading material

https://algocademy.com/blog/fast-and-slow-pointers-a-powerful-technique-for-solving-linked-list-problems/

TODO

Links to this note

Topics and questions for coding challenges