Question

You are given an array of $\mathbf{n}$elements, and you notice that some of the elements are duplicates; that is, they appear more than once in the array. Show how to remove all duplicates from the array in time $\mathbf{O}\mathbf{(}\mathbf{n}\mathbf{}\mathbf{log}\mathbf{}\mathbf{n}\mathbf{)}$ .

Short answer

All duplicates are removed from the array in time: $\mathrm{O}(\mathrm{n}\log \mathrm{n})$

Step-by-step solution

Method-I

We may use pre-processing to eliminate duplicates by sorting the array. Its arrays sort consumes $\mathrm{O}\left(\mathrm{n}\log \mathrm{n}\right)$ time, and then we can verify if the last value is like the present value inside one pass; if it is, we don't display that number; otherwise, we do. We'll be able to get rid of the duplicates this way.

So the total amount of time is $\left(\mathrm{n}\mathrm{Log}\mathrm{n}+1\right)=\mathrm{O}\left(\mathrm{n}\mathrm{Log}\mathrm{n}\right)$

Method-II

We need to perform nested loops if we haven't done the pre-processing yet. We execute one loop over the whole array (assuming index $\mathit{i}$ and for each index $\mathit{i}$ we check to see if the identical element is in the remaining set; if so, we do not print the element; otherwise, we do. Without pre-processing, the complexity will be $\mathrm{O}\left({\mathrm{N}}^2\right).$