Chapter 14, Problem 18RE

Explanation of Solution

Algorithm for removing the duplicates:

• The below is the algorithm to remove the duplicates present in the list and the problem is that the list cannot be sorted because the original order need not to be disturbed.
• Thus a copy of sorted array can be done to have a fast lookup of the duplicate elements.

Algorithm:

• Make a copy of $\text{O}\left(\text{n}\right)$ and perform sort operation in $\text{O}\left(\text{n log}\left(\text{n}\right)\right)$.
• Create a companion Boolean array to be the sorted array and now set all the values present in that array to be false.
• Traverse the array and perform the following n times:
• For each of the element present the binary search is used in the copy in $\text{O}\left(\text{log(n)}\right)$ and then look at the neighbors to find whether the elements are duplicate