# My easy understood solution with O(n) time and O(1) space without modifying the array. With clear explanation.

• ``````public int findDuplicate(int[] nums) {
int ret = -1;
for (int i=0;i<nums.length;i++){
if (nums[Math.abs(nums[i])]< 0){
ret = Math.abs(nums[i]);
break;
}else {
nums[Math.abs(nums[i])] *=-1;
}
}
for (int i=0;i<nums.length;i++){
if (nums[i]<0){
nums[i] *=-1;
}
}
return ret;
}``````

• @echoxiaolee excellent solution!!!

• I literally translate this to Python, and it extends the run time limit

• @echoxiaolee run time error when using input [10000000, 1, 1] slow = 10000000, and fast = nums[10000000], how can you guarantee slow and fast are always valid indexes?

• @changjinglu Kick "Call" for you!

• @lf963
Really good explanation! Thanks a mil!

• The head of this list is 0, I think this one is easier to understand:

``````class Solution {
public:
int findDuplicate(vector<int>& nums) {
if(nums.empty())return 0;

int slow = 0,fast = 0;
while(slow!=fast||slow==0) {
slow = nums[slow];
fast = nums[nums[fast]];
}
slow = 0;
while(slow!=fast) {

slow = nums[slow];
fast = nums[fast];
}
return fast;
}
};
``````

Both the slow node and the fast node start from 0.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.