# Bucket Sort - O(N). Generalize the question - if multiple number can be duplicate, find all duplicates

• The forum has two solutions1) Loop detection, 2) Binary Search. Throw in another idea, O(N), using bucket sort. Consider the number n belong to bucket num[n-1].

When we put each number in their bucket. If duplicate exists, then we should find nums[nums[i]-1]==nums[i], otherwise, we should be able to traverse the array in O(N) time.

``````public class Solution {
public int findDuplicate(int[] nums) {
for(int i=0;i<nums.length;i++){
while(nums[i]!=i+1){
int j = nums[i]-1;
if(nums[i] == nums[j]) return nums[i];
else swap(nums, i, j);
}
}
return 0;
}

private void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}``````

1. You must not modify the array (assume the array is read only).

• this post is only for idea exploration, as the description mentioned. Not necessarily all discussions has to fit 100% of the proposed constrains.

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