Leetcode 287. Find the Duplicate Number
Explanation for Leetcode 287 - Find the Duplicate Number, and its solution in Python.
Problem
Leetcode 287 - Find the Duplicate Number
Example:
1
2
3
4
5
6
7
8
Input: nums = [1,3,4,2,2]
Output: 2
Input: nums = [3,1,3,4,2]
Output: 3
Input: nums = [3,3,3,3,3]
Output: 3
Approach
We can solve this problem like if we were solving array with linked list where each element links to the nums[index]
For example, nums = [1,3,4,2,2], then 1->3->2->4->2->4->2->…. we get infinite loop, thus we can solve this using fast and slow algorithm.
After first loop, we are always going to get distance between intersection to start of cycle and nums[0] to start of cycle is equal.
Let $c$ be the length of cycle, $x$ be distance between intersection to start of cycle, $y$ be distance between 0 to start of cycle.
We also know tha $2*slow = fast$ which is equal to $2(y + c -x) = y + 2c - x$ -> $2y + 2c - 2x = y + 2c - x$ -> $y-x = 0$.
Visualization of the Approach:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
nums = [1,3,4,2,2]
slow, fast = 0, 0
start first iteration
slow = nums[0] = 1
fast = nums[nums[0]] = 3
slow = nums[1] = 3
fast = nums[nums[3]] = 4
slow = nums[3] = 2
fast = nums[nums[4]] = 4
slow = nums[2] = 4
fast = nums[nums[4]] = 4
since slow == fast break
start second iteration
slow = nums[4] = 2
slow2 = nums[0] = 1
slow = nums[2] = 4
slow2 = nums[1] = 3
slow = nums[4] = 2
slow2 = nums[3] = 2
return 2
Here is the Python code for the solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 and Space Complexity
Time Complexity: $O(n)$
Space Complexity: $O(1)$