Find the Duplicate Number
- 2 min read
- LC-Medium
- Linked List
3 years ago
Solution
- The main constraint we must be aware of is the fact that each integer in the array is between [1, n] inclusive
- Think of each value in the array as a pointer to a certain index. If you map this out, you'll get the following linked list:
- From this, the answer we need to return is the node where the cycle begins. In this case, the node is 2
- We also need to notice that the first node won't have any node pointing to it, because the numbers are between [1, n], and 0 is not a part of this range
- We will use this concept to find the start of a cycle, because remember, using Floyd's Tortoise and Hare, once we detect the cycle, we need to find the beginning of the cycle
- Similar to Linked List Cycle, we need to init slow and fast pointers. Move slow one by one, and move fast twice as fast
- Once they meet, move slow back to start of the list (in this case, the node 0)
- Move both pointers at same rate- the point at which they meet is the duplicate number
| Time | Space | Explanation |
|---|---|---|
O(n) | O(1) |
def findDuplicate(self, nums: List[int]) -> int:
# Find intersection point between slow and fast
slow = fast = 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# Create new pointer slow2 that starts from the beginning
# Advance slow and slow2 at same speed- the point at which they meet is the duplicate number
slow2 = 0
while slow != slow2:
slow = nums[slow]
slow2 = nums[slow2]
return slow