TARGET DECK: Leetcode FILE TAGS: Medium
Intuition
Part 1
- This algorithm requires looking up the answer to contemplate it.
- The main idea is that you use the constraints of the problem to formulate the solution.
- What I mean is: since our numbers range from [1, n] inclusive, we can turn our array into a linked list in which we use the values of the array to point to indices 1-n.
- So the value itself can be only from 1-n inclusive.
- Then, we may use the Floyds Tortoise and Hare algorithm to find a meeting point.
Part 2
- Once we have done so, we use math to figure out the 2nd part:
- Then, we note that the slow pointer does 2(p + c - x) iterations, wherein p is how many iterations until the start of the cycle, c is the length of the cycle, and x is the node you have landed on in step 1 (which may or may not be the duplicate element).
- And the fast pointer goes at p + 2c - x, since it loops twice through the cycle until it meets with the slow pointer.
- Solving for these, we get that p = x, or that the number of iterations from the start node (which can never have edges pointing to it) equals the number of iterations from the point you found until the start of the cycle (thereby proving that they must meet).
Cards
START
Basic
Front: Find the Duplicate Number
Back: Create a cycle using fast pointer, slow pointer utilizing fast = nums[nums[fast]], slow = nums[slow], then use equation 2(p + c - x) = p + 2c - x -> p = x
END
Complexity
Runtime
since each time, we are traversing through our array at most 2N times.
Space
since we aren’t using anything but the pointers.
Code
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
slow = fast = 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 slowNotes
