#42 Medium Time O(n) Space O(1) Animated

Find the Duplicate Number

Find a duplicate number in an array of n+1 integers.

LeetCode ↗

Approach: Floyd's Algorithm

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Description

Find a duplicate number in an array of n+1 integers.

Constraints

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

Solution — Floyd's Algorithm

O(n) O(1)

def findDuplicate(nums):
    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

Linked List Cycle

LRU Cache

Find the Duplicate Number

Steps

Description

Constraints

Tags

Solution — Floyd's Algorithm