Given an array of m+n elements in the range 1 to n ie(m elements are repeated). Find the duplicate elements.
Time Complexity: O(m+n)
Space Complexity: O(m)
Solution :
Since we know there are 1 to n elements, we can sort the array in O(n).
The first n elements will be the unique values and n to m will be the duplicates.
This is O(n+m) && no extra space required.
for (int i = 0; i < array.Length; i++)
{
if (array[i] != i + 1)
{
int t = array[array[i]-1];
array[array[i]-1] = array[i];
array[i] = t;
}
}
0 comments:
Post a Comment