Java O(n) time and O(1) space solution. Similar to find loop in linkedlist.


  • 113
    Z

    suppose the array is

    index: 0 1 2 3 4 5

    value: 2 5 1 1 4 3

    first subtract 1 from each element in the array, so it is much easy to understand.
    use the value as pointer. the array becomes:

    index: 0 1 2 3 4 5

    value: 1 4 0 0 3 2

    enter image description here

    Second if the array is

    index: 0 1 2 3 4 5

    value: 0 1 2 4 2 3

    we must choose the last element as the head of the linked list. If we choose 0, we can not detect the cycle.

    Now the problem is the same as find the cycle in linkedlist!

    public int findDuplicate(int[] nums) {
        int n = nums.length;
        for(int i=0;i<nums.length;i++) nums[i]--;
        int slow = n-1;
        int fast = n-1;
        do{
            slow = nums[slow];
            fast = nums[nums[fast]];
        }while(slow != fast);
        slow = n-1;
        while(slow != fast){
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow+1;
    }
    

    One condition is we cannot modify the array. So the solution is

    public int findDuplicate(int[] nums) {
        int n = nums.length;
        int slow = n;
        int fast = n;
        do{
            slow = nums[slow-1];
            fast = nums[nums[fast-1]-1];
        }while(slow != fast);
        slow = n;
        while(slow != fast){
            slow = nums[slow-1];
            fast = nums[fast-1];
        }
        return slow;
    }

  • 3
    M

    Very brilliant !! I tried my best and thought out a binary search O(nlog(n)) solution, but far trivial than yours.
    Great inspire on understanding of array.

    BTW, I think a search for entry block of codes is needed to make sure we get into chain. Like following:

    int entry;
        for (entry = 0; entry < nums.length; entry++)
            if (entry != nums[entry])
                break;

  • 3
    N

    Can someone please explain why there has to be a loop in the presence of a duplicate element when building the graph as described above? You could have a graph with a loop even when no duplicate elements are present. e.g.

    nums = [2 ,1]
    indices = [0 ,1]
    after subtracting 1 from each element in nums = [1, 0]
    there is a cycle because of edges between 0 to 1 and 1 to 0.


  • 0
    W

    How about giving a array like this: 1,4,4,2. Then the 3-->1, and 1-->3, if is it possible to be a death cycle in the first do while?


  • 1
    Z

    Isn't it Tortoise & Hair algorithm to find cycle in a sequence?


  • 0
    Q

    Your input is invalid. It should be 1,3,3,2 as 4 is out of bounds.


  • 2
    H

    Idea is nice but code could be simpler.
    Just start with 0 and no need to deduct 1
    Accepted code (I don't known how to format code in comments):

    public int findDuplicate(int[] nums) {
    int slow = 0, fast = 0;
    do{
    slow = nums[slow];
    fast = nums[nums[fast]];
    }while(slow != fast);
    slow = 0;
    while(slow != fast){
    slow = nums[slow];
    fast = nums[fast];
    }
    return slow;
    }


  • 34
    H

    Nice idea! Code could be simpler: start with 0 and no need to deduct 1.

    Accepted code:

    public int findDuplicate(int[] nums) {
        int slow = 0, fast = 0;
        do{
            slow = nums[slow];
            fast = nums[nums[fast]];
        }while(slow != fast);
        slow = 0;
        while(slow != fast){
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
    

  • 0
    E

    What's about 1 3 2 1? The loop is before the duplicate element. How do we find "1" then?


  • 0
    H

    "What's about 1 3 2 1? The loop is before the duplicate element. How do we find "1" then?"

    index: 0 1 2 3

    value: 1 3 2 1

    list: 0->1->3->1->3->1....


  • 2
    E

    I see.
    Then what about:

    0 1 2 3

    1 2 0 2

    0 -> 1 -> 2 -> 0 -> 1...
    But the dupicate is 2.


  • 1
    J

    Each integer is between 1 and n, not 0 and n.


  • 1
    O

    good explain but no need to deduct 1. It can be started with 0


  • 0
    A

    @nikita [1,2] is invalid input for the given problem.
    Notice that the problem clearly says, range should be from 1 to n, and total no of elements in array to be (n+1).
    If length = 2,
    => n +1 =2,
    => n=1
    => All values in array should be 1.
    Thus [1,2] is invalid.


  • 0
    Y

    @zq670067

    failed on this data:
    [4,3,2,2,5]


  • 0
    E

    @yao18
    Actually, when nums[nums.length-1] == nums.length
    it always fails...


  • 0
    M

    @yao18 The maximum element is nums.length-1, so the test case is invalid. Choosing the last element as the starting point guarantees that we dont start in a cycle, so there are no pathological behaviors.


  • 3
    L

    Similar idea. Also attached the code of Linked List Cycle II. The code of cycle problem is referred to the popular post in the Leetcode discuss.
    Find duplicate num

    public class Solution {
        public int findDuplicate(int[] nums) {
            int slow = 0, fast = 0;
            int len = nums.length;
            while (fast < len && nums[fast] < len) {
                slow = nums[slow];
                fast = nums[nums[fast]];
                if (slow == fast) {
                    slow = 0;
                    while (slow != fast) {
                        slow = nums[slow];
                        fast = nums[fast];
                    }
                    return slow;
                }
            }
            return -1;
        }
    }
    

    Linked List Cycle II

    public class Solution {
        public ListNode detectCycle(ListNode head) {
            if (head == null || head.next == null)  return null;
            ListNode fast = head, slow = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast) {
                    slow = head;
                    while (slow != fast) {
                        slow = slow.next;
                        fast = fast.next;
                    }
                    return slow;
                }
            }
            return null;
        }
    }
    

  • 0
    V

    @mo10 This is actually not required if the slow and fast pointers are started from the end of the array. This is because if the array is of size n+1, then the highest index is n and according to the question, the array contains only numbers till n. As this solution subtracts 1 from every element, the highest number the array can contain is n-1. So the last cell will never point itself.


  • 0
    R
    This post is deleted!

Log in to reply
 

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