Leetcode 287: Find the Duplicate Number

[Medium]

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.

Reading the question

It is easy to solve this question by using sorting or hashmap. However, there is a special requirement that nums can’t be modified and the space capacity has to be O(1). And So, here is a new theory introduced:
Floyd’s Tortoise and Hare (Cycle Detection)

Finding duplicated nodes in a cycle

There is a similar question which is finding the duplicated node in a cycle by using this theory.

Imagine here is the closed loop: [1] -> [2] -> [3] -> [4] -> [1] -> [5] -> [6] ->
By creating 2 pointers:
slowPt: + 1 per step
fastPt: + 3 per step

Steps: start at index=0
slowPt = 2, fastPt = 4
slowPt = 3, fastPt = 6
slowPt = 4, fastPt = 3
slowPt = 1, fastPt = 5
slowPt = 5, fastPt = 2
slowPt = 6, fastPt = 1
slowPt = 1, fastPt = 1

Yay🎉, we find it, the duplicated node is 1, with O(1) memory

Covert a list into a cycle

So, we can apply the same theory to this question. Before using Floyd’s Tortoise and Hare, we have to imagine it as a cycle given that there is a duplicated number exists and so, it has to be a valid cycle.

Let’s use the function f(x) = nums[x] to construct the sequence:
x, nums[x], nums[nums[x]], nums[nums[nums[x]]], ....

By creating 2 pointers:
Using [ 1,3,4,2,2]
1, nums[1]=3, nums[3]=2, nums[2]=4, nums[4]=2,

Steps: start at index = 0 = 1
slowPt = nums[1]=3, fastPt = nums[nums[1]]=2
slowPt = nums[3]=2, fastPt = nums[nums[2]]=2

Yay🎉, we the interaction!

Entrance point

We seems that solved the questions, are we? In fact, the intersection point is not the cycle entrance in the general case. It’s just luck.
The entrance point means the start of the closed cycle, which is our duplicated number!

This time, fastPt will stay in the intersection point and slowPt will back to index=0.

slowPt = nums[1]=3, fastPt = nums[nums[2]]=4
slowPt = nums[3]=2, fastPt = nums[nums[4]]=2

Yay🎉, The solution is 2!

CODE — Python3

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

        #phase 1: find intersaction
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        
        #phase 2: find entrance
        slow = nums[0]
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        
        return slow

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

Thank you for reading! Please comment and let me know how to improve my code!