Start learning free

LESSON 201 OF 347 · SORTING

Remove Duplicates From Array in C#: 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 uniqueVals and push the unique values from nums there.

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

nums[i] has never been seen before if nums[i] != nums[i - 1].

It's time to solve the question with the original constriant. 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 in nums[0]
The second unique value will be stored in nums[1]
...

How can we achieve this?

We will use an index variable p, initially equal to 0, to keep track of where we should place the next unique value we find.

We will traverse nums and check if nums[i] != nums[i - 1]. If so, we will set nums[p] to nums[i] and increment p. What should we return when we finish the traversal?

We should return the subarray nums[0...p].

STEP 1 OF 6

Guided

Ctrl + Enter to check

C# · SORTING

Remove Duplicates From Array in C#, explained

Problem overview

The method RemoveDuplicates receives an int[] and must return an array in which every distinct value appears exactly once. The order of the result is free. For [2, 3, 1, 1, 4, 3, -2, 1], the statement shows [2, 3, 1, 4, -2], and any arrangement of those five values is accepted.

The statement also asks for in-place work with O(1) extra memory and O(n log n) time. So the method must not build a second collection of unique values while scanning. The only new array is the one returned at the end.

Approach: sort, then overwrite from the left

Sorting puts equal values next to each other, so a value is new exactly when it differs from the element before it. A simple version would copy each new value into a second list. That uses O(n) extra space, which the statement rules out.

The in-place version reuses the front of the input array as the output. A write position p marks where the last distinct value was stored. Whenever the scan finds a new value, it advances p and copies the value there. Because p never gets ahead of the scanning index i, the copy never overwrites an element that hasn't been read yet.

On the example, the sorted array is [-2, 1, 1, 1, 2, 3, 3, 4]. The first element stays at index 0, so p starts at 0. Scanning from index 1:

i = 1: 1 differs from -2, so p becomes 1 and nums[1] = 1.
i = 2 and i = 3: 1 equals its neighbour, nothing happens.
i = 4: 2 is new, so p becomes 2 and nums[2] = 2.
i = 5: 3 is new, so p becomes 3 and nums[3] = 3.
i = 6: 3 repeats, nothing happens.
i = 7: 4 is new, so p becomes 4 and nums[4] = 4.

The first p + 1 = 5 elements now hold -2, 1, 2, 3, 4, which is the answer.

Step by step

Sort in place with Array.Sort(nums), so equal values are adjacent.
Set p = 0. It is the index of the last distinct value stored. The first element is always kept, so it is already in place.
Loop from i = 1 while i < nums.Length. The first element needs no check, so the scan starts at the second.
Compare with the previous element: nums[i] != nums[i - 1]. After sorting, this is the test for "met for the first time".
Store the new value. nums[++p] = nums[i] moves p forward first and then writes at the new p.
Return the first p + 1 elements as a new array with Take(p + 1).ToArray(). The count of distinct values is p + 1 because p is an index.

The solution in C#

class Solution {

    public int[] RemoveDuplicates(int[] nums) {
        Array.Sort(nums);
        int p = 0;
        for (int i = 1; i < nums.Length; ++i) {
            if (nums[i] != nums[i - 1]) {
                nums[++p] = nums[i];
            }
        }
        return nums.Take(p + 1).ToArray();
    }
}

The C# details to notice:

Pre-increment. In nums[++p], ++p increases p and then yields the new value. With p++ the index would be the old value, and the first distinct value would be overwritten. The ++i in the loop header behaves the same as i++ there, because its value isn't used.
The array has a fixed size. C# arrays can't shrink, so there is no way to "delete" the tail in place. The method returns a new array holding only the first p + 1 elements. The input array itself keeps its length, and its tail still holds leftover values.
Comparing against nums[i - 1] is safe even though the loop writes into the same array. The write in iteration j goes to an index of at most j, so the element at i - 1 has never been changed by the time iteration i reads it (when a write lands exactly on j, it copies the element onto itself).
Take and ToArray come from System.Linq. Take(n) yields the first n elements and ToArray() copies them into a new array.

Complexity

Time: O(n log n). The sort costs O(n log n). The scan visits each element once.

Space: O(1) beyond the output. The scan uses two integers and overwrites the input array. The returned array is the result itself, not working storage.

Edge cases and common mistakes

All values equal. [5, 5, 5] leaves p at 0, so the result is [5].
No duplicates. [3, 1, 2] sorts to [1, 2, 3] and every element is copied onto itself. The result is [1, 2, 3].
Forgetting to sort. Without sorting, duplicates that aren't neighbours survive: [1, 2, 1] would stay as it is.
Returning p instead of p + 1. That drops the last distinct value.
Using p++ in the store. It writes at the old index and leaves the count off by one.
An empty input. The loop doesn't run and Take(1) of an empty array gives an empty result, so the method returns an empty array.

Testing

[2, 3, 1, 1, 4, 3, -2, 1] gives [-2, 1, 2, 3, 4], the same values as the statement's example in a different order.
[7] gives [7].
[5, 5, 5] gives [5].

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