Description
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and using only constant extra space.
Examples:
Example 1:
Input: nums = [1,3,4,2,2]
Output: 2
Example 2:
Input: nums = [3,1,3,4,2]
Output: 3
Example 3:
Input: nums = [3,3,3,3,3]
Output: 3Solution in Python
Python
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
# Step 1: Initialize the "tortoise" and "hare"
# Both start at the first position of the array
tortoise = hare = nums[0]
# Step 2: Move tortoise by one step, and hare by two steps until they meet
# This is the "cycle detection" part of Floyd's Tortoise and Hare algorithm
while True:
tortoise = nums[tortoise] # Moves by one step
hare = nums[nums[hare]] # Moves by two steps
if tortoise == hare:
break # They meet, indicating the presence of a cycle
# Step 3: To find the entrance to the cycle (the duplicate number)
# Reset one pointer (e.g., tortoise) to the start of the array
tortoise = nums[0]
# Step 4: Move both pointers at the same speed (one step at a time)
# When they meet again, it will be at the duplicate number
while tortoise != hare:
tortoise = nums[tortoise] # Move by one step
hare = nums[hare] # Move by one step
# Step 5: Return the duplicate number
return hareExplanation:
- Initialization: We start by setting both the “tortoise” and “hare” to the first element of the array.
- Cycle Detection:
- The
tortoisemoves one step at a time (nums[tortoise]). - The
haremoves two steps at a time (nums[nums[hare]]). - If there is a duplicate number, they will eventually meet in a cycle, just like in the classic cycle detection problem in a linked list.
- The
- Finding the Duplicate:
- Once a cycle is detected (i.e., when the
tortoiseandharemeet), we reset one pointer (thetortoise) to the start of the array. - Now, both pointers move one step at a time. The point where they meet again is the duplicate number.
- Once a cycle is detected (i.e., when the
- Return the Duplicate: Once they meet again, return the value at that position, which is the duplicate number.
Solution in C++
C++
class Solution {
public:
int findDuplicate(vector<int>& nums) {
// Step 1: Initialize two pointers, "tortoise" and "hare"
// Both start at the first position in the array (nums[0])
int tortoise = nums[0];
int hare = nums[0];
// Step 2: Move the tortoise pointer one step at a time and the hare pointer two steps at a time
// Continue until they meet, which indicates a cycle is found
do {
tortoise = nums[tortoise]; // Moves by one step
hare = nums[nums[hare]]; // Moves by two steps
} while (tortoise != hare); // Stop when both pointers meet
// Step 3: Reset one pointer (tortoise) to the start of the array
tortoise = nums[0];
// Step 4: Move both pointers at the same speed (one step at a time)
// They will meet again at the duplicate number
while (tortoise != hare) {
tortoise = nums[tortoise]; // Move by one step
hare = nums[hare]; // Move by one step
}
// Step 5: Return the duplicate number, which is where both pointers meet
return hare;
}
};Solution in Javascript
JavaScript
var findDuplicate = function(nums) {
// Step 1: Initialize two pointers, "tortoise" and "hare"
// Both start at the first position in the array (nums[0])
let tortoise = nums[0];
let hare = nums[0];
// Step 2: Move the tortoise pointer one step at a time and the hare pointer two steps at a time
// Continue until they meet, indicating a cycle
do {
tortoise = nums[tortoise]; // Move by one step
hare = nums[nums[hare]]; // Move by two steps
} while (tortoise !== hare); // Stop when both pointers meet
// Step 3: Reset one pointer (tortoise) to the start of the array
tortoise = nums[0];
// Step 4: Move both pointers at the same speed (one step at a time)
// They will meet again at the duplicate number
while (tortoise !== hare) {
tortoise = nums[tortoise]; // Move by one step
hare = nums[hare]; // Move by one step
}
// Step 5: Return the duplicate number, which is where both pointers meet
return hare;
};Solution in Java
Java
class Solution {
public int findDuplicate(int[] nums) {
// Step 1: Initialize two pointers, "tortoise" and "hare"
// Both start at the first position in the array (nums[0])
int tortoise = nums[0];
int hare = nums[0];
// Step 2: Move the tortoise pointer one step at a time and the hare pointer two steps at a time
// Continue until they meet, which indicates a cycle is detected
do {
tortoise = nums[tortoise]; // Move by one step
hare = nums[nums[hare]]; // Move by two steps
} while (tortoise != hare); // Stop when both pointers meet
// Step 3: Reset one pointer (tortoise) to the start of the array
tortoise = nums[0];
// Step 4: Move both pointers at the same speed (one step at a time)
// They will meet again at the duplicate number
while (tortoise != hare) {
tortoise = nums[tortoise]; // Move by one step
hare = nums[hare]; // Move by one step
}
// Step 5: Return the duplicate number, which is where both pointers meet
return hare;
}
}