My easy understood solution with O(n) time and O(1) space without modifying the array. With clear explanation.


  • 445
    E

    The main idea is the same with problem Linked List Cycle II,https://leetcode.com/problems/linked-list-cycle-ii/. Use two pointers the fast and the slow. The fast one goes forward two steps each time, while the slow one goes only step each time. They must meet the same item when slow==fast. In fact, they meet in a circle, the duplicate number must be the entry point of the circle when visiting the array from nums[0]. Next we just need to find the entry point. We use a point(we can use the fast one before) to visit form begining with one step each time, do the same job to slow. When fast==slow, they meet at the entry point of the circle. The easy understood code is as follows.

    int findDuplicate3(vector<int>& nums)
    {
    	if (nums.size() > 1)
    	{
    		int slow = nums[0];
    		int fast = nums[nums[0]];
    		while (slow != fast)
    		{
    			slow = nums[slow];
    			fast = nums[nums[fast]];
    		}
    
    		fast = 0;
    		while (fast != slow)
    		{
    			fast = nums[fast];
    			slow = nums[slow];
    		}
    		return slow;
    	}
    	return -1;
    }

  • 9
    class Solution(Thread):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
      
        slow = nums[0]
        fast = nums[nums[0]]
        while (slow != fast):
            slow = nums[slow]
            fast = nums[nums[fast]]
    
        fast = 0;
        while (fast != slow):
            fast = nums[fast]
            slow = nums[slow]
            
        return slow
    

  • 3

    Thank your answer!


  • 8
    T

    Can you explain why in the second loop the two are guaranteed to meet?


  • 33
    Z

    Bravo @echoxiaolee. @tsenmu this is guarentted if you understand the problem #142 very well. Please note the constraint in the problem " array nums containing n + 1 integers where each integer is between 1 and n (inclusive)" makes the array an abstracted linked list: n[x] -> y. Now since integer cannot be 0, item 0 is guarenteed to be a "node" outside any cycle because n[x] must be larger than 0. Then the 1st fast-slow traverse is guranteed to have the meet point at equally distance from the common starting point (0) to the cycle entry point


  • 0
    Z

    An impressive solution! Thx so much!


  • 20
    J

    I don't understand. If nums[3] = 3, and the high/slow gets to the nums[3], it will get stuck at nums[3], how can the algorithm detect the duplicate?

    Can anyone help?


  • 0
    Z
    This post is deleted!

  • 15
    Z

    @jun16 If nums[3] = 3, you must have an entry to 3. For the first step is 0, and then it may cost some steps to 3 and then the duplicate number is 3 for you have an entry number and 3 both points to 3. Actually 3->3 is the cycle but a really small cycle. The entry must point to the entry of the cycle, at least two of the array point to the entry number.


  • 79
    C

    Thanks for your method.
    Let me try to prove it.

    When they meet, assume slow tag move s steps, fast tag move 2s steps, the circle length is c.
    There must be:

    2s = s + n*c

    => s = n*c....(1)

    Then, assume the length from start point to entry point is x, and the length from the entry
    point to the meet point is a.
    There must be: s = x+a....(2)

    So, from (1) and (2)

    x+a = s = n*c

    => x+a = n*c

    => x+a = (n-1)*c+c

    => x = (n-1)*c+c-a

    c-a means the length from the meetpoint to the entry point.

    LHS means: the new tag from start point move x steps.

    RHS means: the slow tag moves (n-1) cycles plus the length from the meetpoint to the entry point.

    So, we can get the entry point when the new tag meet the slow tag.


  • 0
    This post is deleted!

  • 0
    E

    @zhaoguojie2010@163.com, Please pay attention to the original question description, "an array nums containing n + 1 integers where each integer is between 1 and n (inclusive)". As for your case, the largest number can only be 8 instead of 9.


  • 0

    many thanks~~~~~~~~~~~~~


  • 0

    Excellent solution!


  • 0
    H

    wow, clever!


  • 3
    G

    Excellent idea. I am trying to understand how it works:

    1. Suppose there is "m" steps from nums[0] to entry point, and the length of circle is "n" steps.

    2. When slow arrives entry point after m steps, the fast has advanced (2m+1) steps

      slow = m

      fast = 2m+1

    3. The distance from slow to fast in the circle is:

      D = (C*n + slow) - fast

      = C*n - (m + 1)
      

      where C = ceil(m/n)

    4. Since fast needs D steps to catch up with slow, the distance from meet point to entry point is D as well.

    5. After (m+1) steps, slow would be sure at the entry point:

      D1 = D + (m+1) = C*n

    6. At the second loop, fast should start from 0 rather than num[0], so that it would arrive entry point after (m+1) steps.


  • 29
    Y

    @jun16 There could be multiple cycles in our 'graph'. But the beauty of this problem is that nums[0] is always the entrance to the cycle which has duplicate numbers, because no one can jump back to nums[0]. See the example below. index = [0 1 2 3 4 5 6 7]; nums=[5 2 1 3 5 7 6 4]. nums[1] and nums[2] forms an isolated cycle. nums[3]=3 forms an isolated cycle. nums[6]=6 forms an isolated cycle. nums[5] nums[7] nums[4] forms a cycle and nums[0]=5 is an entrance to the cycle.


  • 0
    S

    I'm not clear how the first loop realise the cycle detection?
    "slow = nums[slow]; " the slow pointer doesn't mobe one step each time?
    and the fast pointer doesn't move two step each time?
    for example:
    index = [0 1 2 3 4 5 6 7]; nums=[5 2 1 3 5 7 6 4].
    slow = 5 7 4;
    fast = 7 5 4;

    I can understand if 5->2->1->3->5(the circle occur,discard the rest sequence),
    slow change as: 5 2 1 3 5;
    fast change as: 5 1 5 1 5;
    they meet at 5;
    but i can't understand the mechanism of the first loop?
    any one explain?


  • 13
    Y

    @susandebug The first while loop ensures you goes in the correct cycle which has duplicates. for example: index = [0 1 2 3 4 5 6 7]; nums=[5 2 1 3 5 7 6 4]. (slow)nums[slow] = (0)5 (5)7 (7)4 (4)5; fast = (0)5 (7)4 (5)7 (4)5; ----> when they meets at (idx=4)(value=5), you know you have a cycle.

    Take a look at the cycle by the indices and values:

    idx: 0--->5--->7--->4-->(goes back to idx=5)

    val: 5--->7--->4--->5-->(goes back to val=7)

    The second while loop will stop when "fast=0" and "slow=4" (their values = 5, the duplicate number). The duplicate number 5 is the reason why the two pointers will meet at a same index (next number). In fact, the second loop will always stop right before they meet at the first item of the cycle. (This is very similar to the problem Linked List Cycle II. )


  • 0
    S

    @yuanwen2 thanks for your delatiled explaination. Now I can understand the slow pointer is the index of the nums and the faster is the val of the nums, but I still can't understand the mechanism to detect the cycle.
    I understand the problem Linked List Cycle II. but the first loop is not the same, would you please do futher expalination,thanks,:)


Log in to reply
 

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