Problem URL: Find the duplicate number

We will use Floyd's cycle detection algorithm for solve the problem. As the input array has elements from [1, n], and there is n+1 numbers, this is nothing but a linked list, where the list starts as index 0, and the list has a cycle. We will find the first element of the cycle.

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow, fast = 0, 0
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        slow2 = 0
        while True:
            slow = nums[slow]
            slow2 = nums[slow2]
            if slow == slow2:
                return slow

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