Question

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

Answer 1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

A simple modification to merge sort will do the trick. Merge sort is O(n log n). It's also stable, meaning that items with equal keys will remain in their same relative order. The only difference here is that you want to eliminate duplicates. The only change to the code is in the comparison and copying of items.

You would modify the code so you don't copy equal items:

while (leftIndex < leftMax && rightIndex < rightMax)
{
    if (a[leftIndex] < a[rightIndex])
    {
        output[outputIndex] = a[leftIndex];
        ++leftIndex;
    }
    else if (a[leftIndex] > a[rightIndex])
    {
        output[outputIndex] = a[rightIndex];
        ++rightIndex;
    }
    else
    {
        // items are equal.
        // increment the right, but don't copy anything
        ++rightIndex;
    }
}

You could also do this with a standard merge sort and then do a final pass over the sorted array to remove duplicates.

Kindly revert for any queries

Thanks.