Floyd's Tortoise and Hare (Cycle Detection) algorithm

This algorithm is commonly used to detect cycles in a linked list but can also be adapted to find duplicates in an array.

Floyd's Cycle Detection Algorithm, also known as the "tortoise and hare" algorithm, is a popular method for detecting cycles in a sequence, such as a linked list or an array. It's named after Robert W. Floyd, who introduced it in 1967.

The basic idea behind this algorithm is to use two pointers, one moving slower than the other, and check whether they eventually meet. If they do meet, it indicates the presence of a cycle. Here's a detailed explanation of how the algorithm works:

Algorithm Overview:

1. Initialize two pointers, often called the "slow" and "fast" pointers, to the starting point of the sequence.

2. Move the slow pointer one step at a time and the fast pointer two steps at a time through the sequence.

3. If there is a cycle in the sequence, the fast pointer will eventually catch up to the slow pointer. This happens because the fast pointer is moving twice as fast as the slow pointer.

4. Once the two pointers meet, reset one of the pointers (usually the fast pointer) to the starting point of the sequence and keep the other pointer where it is.

5. Move both pointers at the same pace (one step at a time) until they meet again. The point where they meet is the starting point of the cycle.

Detailed Explanation:

Let's break down each step in more detail:

1. Initialization: Initially, both the slow and fast pointers start at the beginning of the sequence.

2. Movement: In each iteration, the slow pointer advances by one step, and the fast pointer advances by two steps. If there is no cycle, the fast pointer will reach the end of the sequence or exit the sequence. However, if there is a cycle, the fast pointer will eventually enter the cycle and start circling within it.

3. Cycle Detection: If there is a cycle, the fast pointer will eventually catch up to the slow pointer. This is because the fast pointer is covering more ground in each iteration. The fast pointer may take a few iterations to catch up, depending on the length of the non-cyclic part of the sequence.

4. Cycle Confirmation: Once the fast pointer catches up to the slow pointer, it means that the two pointers are now within the cycle. This is the first point of intersection.

5. Cycle Length Determination: To find the starting point of the cycle, one of the pointers (usually the fast pointer) is reset to the beginning of the sequence. The other pointer remains at the intersection point.

6. Collision Point: Both pointers are moved one step at a time. They will meet again at the starting point of the cycle. The number of steps required for them to meet again is equal to the distance between the starting point of the cycle and the intersection point.

Key Properties:

• The fast pointer moves twice as fast as the slow pointer.

• The distance between the starting point of the cycle and the intersection point is equal to the distance between the beginning of the sequence and the starting point of the cycle.

Complexity:

Floyd's Cycle Detection Algorithm runs in linear time, O(n), where n is the length of the sequence. It uses only two pointers and a constant amount of additional space, making it a memory-efficient way to detect cycles in sequences. This algorithm is widely used for cycle detection in linked lists, arrays, and other data structures.

code example:

InterviewBit easy-level question: Find Duplicate in Array

c++ solution of the question:

int Solution::repeatedNumber(const vector<int> &A) {
    int fast = A[0], slow = A[0];

    do{
        slow = A[slow];
        fast = A[A[fast]];
        // move slow:1 step and fast: 2 step
    }while(fast != slow);// till they meet at some point depicting a cyclic loop

    // when the loop is found, re-initialize the fast iterator at the starting 
    // and let the slow continue from where it was left 
    fast = A[0];
    while(fast != slow){
        fast = A[fast];
        slow = A[slow];
    }

    return (slow < 1 ? -1: slow);
}