Tortoise & Haire cycle detection algorithm


  • 16
    Z

    O(n) time O(1) space solution -

    public class Solution {
        public static int findDuplicate(int[] nums) {
            //using Tortoise & Hair algorithm by Donald Knuth to find cycle in a sequence.
            //This algorithm also called Floyd's cycele detection algorithm
            int n = nums.length;
            int tortoise = n;
            int hair = n;
            
           do{
                tortoise = nums[tortoise-1];
                hair = nums[nums[hair-1]-1];
            } while(hair != tortoise);
            
            //find the starting point of the cycle
            //int mu = 0;
            tortoise = n;
            while(hair != tortoise){
                tortoise = nums[tortoise-1];
                hair = nums[hair-1];
                //mu++;
            }
            
            return tortoise;
        }
    }

  • 2
    J

    I am not sure if the algorithm handles the case where nums[n-1] = n.

    Could anyone help clarify?


  • 0
    M

    In that case, n must be the duplicated number.


  • 0
    C

    this case can be handled. There are two situations: situation A: the n is not the duplicated num, then it shall be isolated, neither slow or fast pointer can visit it, e.g 3, 2, 1, 1. So it will not impact the algorithm. situation B: n is the duplicated num, e.g 3, 2, 2, 1, for sure it can be solved by the algorithm


  • 0
    N

    it definitely doesn't work with [1,2,2,4].


  • 0
    C

    This test case is incorrect according to the question.


  • 0
    E

    The input must meet the requirement that the size of the largest element in the array should be less than the length of array. For example, [1, 2, 2, 3] the length is 4, the largest element should be less than 4 which is 3. So [1, 2, 2, 4] is a invalid input according to the question.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.