LeetCode Solutions
287. Find the Duplicate Number
Time: $O(n)$ Space: $O(1)$
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow = nums[nums[0]];
int fast = nums[nums[nums[0]]];
while (slow != fast) {
slow = nums[slow];
fast = nums[nums[fast]];
}
slow = nums[0];
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
};
class Solution {
public int findDuplicate(int[] nums) {
int slow = nums[nums[0]];
int fast = nums[nums[nums[0]]];
while (slow != fast) {
slow = nums[slow];
fast = nums[nums[fast]];
}
slow = nums[0];
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
slow = nums[nums[0]]
fast = nums[nums[nums[0]]]
while slow != fast:
slow = nums[slow]
fast = nums[nums[fast]]
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow