Tortoise & Haire cycle detection algorithm

  • 16

    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;
                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];
            return tortoise;

  • 2

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

    Could anyone help clarify?

  • 0

    In that case, n must be the duplicated number.

  • 0

    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

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

  • 0

    This test case is incorrect according to the question.

  • 0

    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.