If you are allowed to change the order of the elements then it's easy. You do a quicksort so that all duplicates will appear one after the other. Quicksort doesn't create a temporary array so you are not violing any condition. Its execution time is actually O(n log n), so you might run into trouble for that. And removing duplicates from a sorted container is pretty easy.