Find Duplicate

Medium

Python

def find_duplicate(nums):
    slow=fast=nums[0]
    while True:
        slow=nums[slow]; fast=nums[nums[fast]]
        if slow==fast: break
    slow=nums[0]
    while slow!=fast: slow=nums[slow]; fast=nums[fast]
    return slow

Java

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

Key Insight

Floyd's cycle. Java do-while vs Python while True+break.

Python → Java Differences

while True+break vs do-while
Java has do-while Python does not
Floyd's cycle identical

Python

def find_duplicate(nums):
    slow=fast=nums[0]
    while True:
        slow=nums[slow]; fast=nums[nums[fast]]
        if slow==fast: break
    slow=nums[0]
    while slow!=fast: slow=nums[slow]; fast=nums[fast]
    return slow

Java

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

Algorithm Steps

1. Find cycle meeting point
2. Find cycle start

← Previous All Arrays Next →