C O(n) solution, beats 91%, two pointers method


  • 1
    A
    int findDuplicate(int* nums, int numsSize) {
        //start with last elem, follow with two pointers, fast and slow, until they collide.  from that point and from the last elem, walk along again until pointers coincide.
        
        int slow=nums[0],fast=nums[nums[0]],prev;
        while(slow != fast){
            slow=nums[slow];// slow equals index stored at slow
            fast=nums[nums[fast]];// fast equals index stored at index stored at fast
        }
        slow=0;
        while(slow != fast){
            prev=slow;
            fast=nums[fast];
            slow=nums[slow];
        }
        return nums[prev];
    }
    

Log in to reply
 

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