Start learning free

LESSON 228 OF 414 · SORTING

Remove Duplicates From Array in Rust: Sort and Compact In Place

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 6
    Ctrl + Enter to check

    RUST · SORTING

    Remove Duplicates From Array in Rust, explained

    Problem overview

    The function remove_duplicates receives a vector of integers, nums, and returns a vector in which each distinct value appears exactly once. The order of the result is free. The statement asks for O(n log n) time and O(1) extra space, with no second vector for the unique values.

    For nums = [2, 3, 1, 1, 4, 3, -2, 1] the distinct values are -2, 1, 2, 3 and 4. This solution returns them in ascending order, [-2, 1, 2, 3, 4], which is one of the allowed orders.

    Approach: sort, then overwrite from the left

    An earlier lesson on this problem collects unique values into a new vector and checks membership by scanning it, which takes O(n^2) time and O(n) extra space. Here sorting does both jobs better.

    After sorting, equal values are neighbours, so a value is new exactly when it differs from the last value kept. The solution walks through the sorted vector and keeps a write index, p, which marks the position of the last unique value stored at the front of the vector. When the scan finds a value different from nums[p], it moves p one step forward and copies the value there. Duplicates are skipped. The front part nums[0..=p] then always holds the unique values found so far, in order, with no repeats.

    Writing to the front never destroys a value that is still needed, because the write position p is never ahead of the read position i. At the end, everything after index p is leftover, and the vector is cut to p + 1 elements.

    Here is the vector as the loop runs on the sorted example [-2, 1, 1, 1, 2, 3, 3, 4]:

    i=1 p=1 [-2, 1, 1, 1, 2, 3, 3, 4]
i=2 p=1 [-2, 1, 1, 1, 2, 3, 3, 4]
i=3 p=1 [-2, 1, 1, 1, 2, 3, 3, 4]
i=4 p=2 [-2, 1, 2, 1, 2, 3, 3, 4]
i=5 p=3 [-2, 1, 2, 3, 2, 3, 3, 4]
i=6 p=3 [-2, 1, 2, 3, 2, 3, 3, 4]
i=7 p=4 [-2, 1, 2, 3, 4, 3, 3, 4]

    After the loop, p is 4, and cutting to 5 elements leaves [-2, 1, 2, 3, 4].

    Step by step

    1. Make the vector mutable and sort it. Shadow the parameter with let mut nums = nums;, which moves the vector into a new mutable binding without copying it. Then call sort(), so equal values end up together.
    2. Guard the empty vector. The first element is always kept, so the code after the guard assumes at least one element. For an empty vector, return it as it is.
    3. Create the write index. Declare p as a mutable usize starting at 0: the position of the last distinct value kept. The first element is already in place.
    4. Loop over the rest with i in 1..nums.len().
    5. Compare with the last kept value. If nums[i] differs from nums[p], it is met for the first time. Comparing with nums[i - 1] would give the same answer here, because in a sorted vector both hold the latest value.
    6. Store it. Increment p first with p += 1, then copy nums[i] into nums[p].
    7. Cut the leftovers. After the loop, call truncate(p + 1) to keep only the first p + 1 elements, and return nums.

    The solution in Rust

    impl Solution {
    fn remove_duplicates(nums: Vec<i32>) -> Vec<i32> {
        let mut nums = nums;
        nums.sort();
        if nums.is_empty() {
            return nums;
        }
        let mut p = 0usize;
        for i in 1..nums.len() {
            if nums[i] != nums[p] {
                p += 1;
                nums[p] = nums[i];
            }
        }
        nums.truncate(p + 1);
        nums
    }
}

    The Rust details worth a closer look:

    • Shadowing. let mut nums = nums; declares a new variable with the same name. The old, immutable binding is moved into it. This is a common way to make a parameter mutable without changing the function signature, and it copies nothing.
    • Copying an element. nums[p] = nums[i]; reads one element and writes another in the same vector. This is allowed because i32 is Copy: the right side is evaluated to a plain number before the write begins, so no two borrows overlap.
    • truncate. nums.truncate(n) keeps the first n elements and drops the rest. If n is larger than the length, it does nothing. It changes the length but keeps the allocation, so no memory moves.
    • The empty check. For an empty vector, 1..nums.len() is the empty range 1..0 and truncate(1) does nothing, so the function would return [] even without the guard. The guard makes the assumption explicit: from there on, nums[0] exists.
    • The type of p. Vector indices are usize, and writing 0usize fixes the type of p explicitly.

    Complexity

    Time: O(n log n). Sorting takes O(n log n). The loop does one comparison and at most one copy per element, which is O(n). truncate on integers is constant time.

    Space. The compaction writes into the same vector and keeps only a few integers. Rust's stable sort() may use a temporary buffer, so strictly its extra space can be O(n). Calling sort_unstable() instead sorts without a buffer, and gives the same result for integers.

    Edge cases and common mistakes

    • Empty vector. The guard returns it unchanged, [].
    • One element. The loop doesn't run, p stays 0, and truncate(1) leaves [9] as it was.
    • All values equal. For [5, 5, 5] the condition never fires, p stays 0, and the result is [5].
    • Forgetting the + 1. p is an index, not a count. truncate(p) would drop the last unique value.
    • Copying before moving p. Writing nums[p] = nums[i] before p += 1 overwrites the last unique value instead of the slot after it.
    • Not sorting first. Without sorting, the same value can appear in separate places, and comparing with the last kept value no longer finds every duplicate. For [1, 2, 1] the result would be [1, 2, 1].

    Testing

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