CareerCup

In java, I think you can add the array elements to a Set (this data structure does not allow duplicates) and print the contents of the array

I'm completely new to data structures, correct me if I'm wrong.

In java, I think you can add the array elements to a Set (this data structure does not allow duplicates) and print the contents of the array

I'm completely new to data structures, correct me if I'm wrong.

This can't be done in linear time if the array has numbers in random order. It has been proven the uniqueness/duplicacy finding is nlogn time in the worst case.
It array is sorted then a linear solution is pretty easy.

If we know the range of numbers existing in this array (lets say m to n) then we can have an Hash Table with indexes m to n with all items set to zero(0) to start off with. Now, run through the given array and set the corresponding items to true (1) in the hash table. If the value in hash table already = 1 then don't print that item in the array and move ahead. This way we we can print the array elements skipping the duplicates in linear time.

time complexity cannot be linear in worst case without increasing the memory requirements.... otherwise the soln by Nils is appropriate....

Hi,

You can use Radix sort. Assuming integers, you can say that the memory consumption is 0(1) in the sense it doesnt depend upon the input N (which is the size of the array). After having done that, you can find the duplicates in O(n).

Thanks,
Rohith Menon.