Start learning free

LESSON 220 OF 409 · SORTING

Remove Duplicates from Array in C++: Sort and Compact in O(n log n)

Practice O(n log n) Read the full explanation

Given an array of integers, remove the duplicates in-place such that each unique element appears only once.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

The resulting array can be in any order.

Example:

Input: [2, 3, 1, 1, 4, 3, -2, 1]
Output: [2, 3, 1, 4, -2]

Note:

Your algorithm should run in O(n log n) time and use O(1) extra space.


Hints:

Let's sort the array in non-decreasing order. In this way all the equal elements will come one after another. Also, let's remove the O(1) extra space constraint for now to make the problem easier. Let's use an extra array uniqueValues and add the unique values from nums there.

Then, we can traverse the sorted array nums from left to right using an index i. We should add the element at index i into uniqueValues only if that value has not been seen before. How can we check this?

The element at index i has never been seen before if it is different from the element at index i - 1.

It's time to solve the question with the original constraint. We will still traverse sorted nums but each time we find a new unique element, we will overwrite an element of nums with this value, starting from the left:
  • The first unique value will be stored at index 0 of nums
  • The second unique value will be stored at index 1
  • ...
How can we achieve this?

We will use an index variable p, initially equal to 0, to keep track of the index where the last unique value was placed.

We will traverse nums and check if the element at index i is different from the element at index i - 1. If so, we will increment p and then copy the element at index i to index p. What should we return when we finish the traversal?

We should return the first p + 1 elements of nums.

STEP 1 OF 7
    Ctrl + Enter to check

    C++ · SORTING

    Remove Duplicates From Array in C++, explained

    Problem overview

    The method removeDuplicates(vector<int>& nums) takes an unsorted vector and must leave each distinct value in it exactly once. The result may be in any order. The statement asks for the work to be done in place, with O(1) extra memory and O(n log n) time.

    For [2, 3, 1, 1, 4, 3, -2, 1] the distinct values are 2, 3, 1, 4 and -2, so any ordering of those five is accepted. The solution below returns them sorted: [-2, 1, 2, 3, 4].

    Approach: sort, then keep the first copy of each value

    With unsorted data, finding out whether a value was seen before means remembering all earlier values, which costs extra memory (a hash set), or scanning everything before it, which makes the whole job O(n²). Sorting removes the problem. After sorting, equal values sit next to each other, so a value is new exactly when it differs from its left neighbour.

    The in-place part uses two positions. The reading index i walks over the sorted vector. The writing index p marks where the last distinct value was stored. Each time nums[i] differs from nums[i - 1], the loop moves p one step right and copies nums[i] there. The distinct values gather at the front of the vector, in order, and p + 1 is how many there are. Since p never gets ahead of i, nothing is overwritten before it has been read.

    Take the sorted vector [-2, 1, 1, 1, 2, 3, 3, 4], with p = 0 at the start:

    • i = 1: 1 differs from -2, so p becomes 1 and nums[1] = 1.
    • i = 2 and i = 3: the value is 1 again, so nothing happens.
    • i = 4: 2 is new, so p = 2 and nums[2] = 2.
    • i = 5: 3 is new, so p = 3 and nums[3] = 3.
    • i = 6: 3 repeats; nothing happens.
    • i = 7: 4 is new, so p = 4 and nums[4] = 4.

    The front of the vector reads -2, 1, 2, 3, 4. With p = 4, the vector is cut to p + 1 = 5 elements.

    Step by step

    1. Handle an empty vector first. The rest of the function treats nums[0] as a kept value. On an empty vector, the final resize(p + 1) would grow it to one element and return {0}, so return early instead.
    2. Sort with sort(nums.begin(), nums.end()). It takes the range as a pair of iterators.
    3. Set p = 0. The first element is always kept, so it is already in place.
    4. Loop from i = 1 to the end of the vector.
    5. Compare with the previous element: nums[i] != nums[i - 1] means a new value.
    6. Store it with nums[++p] = nums[i]. The pre-increment raises p first and then uses the new value as the index.
    7. Shrink and return. nums.resize(p + 1) drops the leftover tail, and the function returns nums.

    The solution in C++

    class Solution {
public:
    vector<int> removeDuplicates(vector<int>& nums) {
        if (nums.empty()) {
            return nums;
        }
        sort(nums.begin(), nums.end());
        int p = 0;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] != nums[i - 1]) {
                nums[++p] = nums[i];
            }
        }
        nums.resize(p + 1);
        return nums;
    }
};

    Some C++ details:

    • The parameter is a reference. vector<int>& nums means the caller's vector is sorted and shrunk in place. The function also returns nums by value, which makes a copy for the return. That copy is a separate vector the size of the result, so strictly the extra memory is not O(1) for the returned value. The work on nums itself uses only p and i.
    • resize to a smaller size erases elements from the end. It is the C++ way to cut a vector, since there is no way to "return a prefix" of an array.
    • nums.size() is unsigned. Comparing it with the int i is fine for non-negative values and the loop is safe, though compilers may warn about the mixed types.
    • The standard library has this idiom. nums.erase(unique(nums.begin(), nums.end()), nums.end()) after sort does the same job: unique moves the distinct values to the front and returns an iterator to the end of them, and erase cuts the tail. It is worth knowing, and it is what to write outside this lesson.

    Complexity

    Time: O(n log n). std::sort takes O(n log n) comparisons. The compaction loop is a single O(n) pass, and the final resize only removes elements. The sort dominates.

    Space: O(1) extra beyond the input vector, apart from the small stack space the sort uses internally. Everything else is two integers.

    If the order does not matter and extra memory is allowed, a set or unordered_set removes duplicates without sorting. An unordered_set takes O(n) time on average and O(n) space, and it can keep the original order if you only append values that insert reports as new. This lesson trades that memory for a sort.

    Edge cases and common mistakes

    • Empty vector. The early return handles it. Without it, resize(1) would produce {0}, a value that was never in the input.
    • One element. The loop does not run, p stays 0, and the vector is unchanged.
    • All values equal. [7, 7, 7] becomes [7].
    • Forgetting to sort. Comparing with the previous element only catches adjacent repeats. On [1, 2, 1] without sorting, nothing would be removed.
    • Forgetting resize. The distinct values are at the front, but stale values remain after position p. The vector would still have its old length.

    Testing

    • [2, 3, 1, 1, 4, 3, -2, 1] gives [-2, 1, 2, 3, 4].
    • [] gives [].
    • [5] gives [5].
    • [7, 7, 7] gives [7].
    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free