How to find duplicate element in an array with minimum time complexity
Last week i appeared for an interview with well-known product based company the person taking interview asked questions related to data structure, caching and optimization. So they asked the question how to find the duplicate element in an array with minimum complexity.
There is multiple approach to solve this problem.
1. Let’s first demostrate naive approach to solve this problem. Use two for loops compare the element you find the duplicate element. But in that case complexity is o(n2).
for(i = 0; i < size(array); i++)
for(j = i+1; j < size(array); j++)
if(arr[i] == arr[j])
printf(" %d ", arr[i]);
2. Second approach is optimized one compare to first approach. Count the array. Traverse the array once, while traversing the array keep the count. Time complexity of this method is O(n).
for(k = 0; k < size(array); k++)
if(count[array[k]] == 1)
printf(" %d ", arr[k]);
3. You can also solve this problem using hashing.