LeetCode: 287. Find the Duplicate Number

As a novice, it was not easy at all for me to solve this problem. I relied on other people's explanations and codes, and this post is to summarize their ideas.

 

It is very tricky to solve this problem within O(N) time & O(1) memory. (* without modifying the array)

The best way is "Floyd's Algorithm" as this problem can be seen as a linked list with a cycle.

Check out the below video for further explanations.

https://www.youtube.com/watch?v=wjYnzkAhcNk&t=876s 

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 1
        slow, fast = nums[0], nums[nums[0]]
        while slow != fast:
            slow = nums[slow]
            fast = nums[nums[fast]]
        p1, p2 = 0, slow
        while p1 != p2:
            p1 = nums[p1]
            p2 = nums[p2]
        return p1

 

Another solution is using binary search.

This algorithm's time complexity is O(NlogN), but this solution is more thinkable in my opinion. (As it is almost impossible to come up with Floyd's algorithm when facing this problem for the first time except for the most brilliant guys).

If the code below is not intuitive or easy to understand, the link below will be helpful.

https://leetcode.com/problems/find-the-duplicate-number/discuss/72844/Two-Solutions-(with-explanation)%3A-O(nlog(n))-and-O(n)-time-O(1)-space-without-changing-the-input-array 

Two Solutions (with explanation): O(nlog(n)) and O(n) time , O(1) space, without changing the input array - LeetCode Discuss

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        low, high = 1, len(nums) - 1
        while low < high:
            mid = (low + high) // 2
            cnt = 0
            for num in nums:
                if num <= mid:
                    cnt += 1
            if cnt <= mid:
                low = mid + 1
            else:
                high = mid
        return low