Find the Duplicate Number - LeetCode Daily Challenge

Problem Statement

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

Example 1

Input: nums = [1,3,4,2,2]
Output: 2

Example 2

Input: nums = [3,1,3,4,2]
Output: 3

Try here before watching the video.

Prerequisite

Video Explanation

Java Code

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0];
        int 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;
    }
}

C++ Code

#include <vector>
using namespace std;

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0];
        int 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;
    }
};

Python Code

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = nums[0]
        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

Javascript Code

var findDuplicate = function(nums) {
    let slow = nums[0];
    let 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;
};

Go Code

func findDuplicate(nums []int) int {
    slow := nums[0]
    fast := nums[0]

    for {
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast {
            break
        }
    }

    slow = nums[0]

    for slow != fast {
        slow = nums[slow]
        fast = nums[fast]
    }

    return slow
}

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)