LeetCode Entry
287. Find the Duplicate Number
Duplicate single number in 1..n array, no extra memory
287. Find the Duplicate Number medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/548
Problem TLDR
Duplicate single number in 1..n array, no extra memory #medium
Intuition
The idea of existing cycle would come to mind after some hitting your head against the wall. The interesting fact is we must find the node that is not a port of the cycle: so the meeting point will be our answer:
Now the clever trick is we can treat node 0 as this external node:
This will coincidentally make our code much cleaner, I think this was the intention of the question authors.
Approach
Draw some circles and arrows, walk the algorithm with your hands. To find the meeting point you must reset one pointer to the start.
- The Rust’s
do-while-doloop is perfectly legal https://programming-idioms.org/idiom/78/do-while-loop/795/rust
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun findDuplicate(nums: IntArray): Int {
var fast = 0; var slow = 0
do {
fast = nums[nums[fast]]
slow = nums[slow]
} while (fast != slow)
slow = 0
while (fast != slow) {
fast = nums[fast]
slow = nums[slow]
}
return slow
}
pub fn find_duplicate(nums: Vec<i32>) -> i32 {
let (mut tortoise, mut hare) = (0, 0);
while {
hare = nums[nums[hare as usize] as usize];
tortoise = nums[tortoise as usize];
hare != tortoise
}{}
hare = 0;
while (hare != tortoise) {
hare = nums[hare as usize];
tortoise = nums[tortoise as usize]
}
tortoise
}