LESSON 225 OF 414 · SORTING

Remove Duplicates From Array in Scala: O(n log n) with Sorting

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

Guided

Ctrl + Enter to check

Remove Duplicates From Array in Scala, explained

Problem overview

The method removeDuplicates receives an array of integers and returns an array in which every distinct value appears once. The order of the result doesn't matter. For [2, 3, 1, 1, 4, 3, -2, 1] the distinct values are 2, 3, 1, 4 and -2, so any arrangement of those five numbers is correct.

Approach: sort, then compact

A simple idea is to keep a second array and add each value to it only if it hasn't been added yet. Checking "has it been added?" is slow on an unsorted array. Sorting fixes that: equal values become neighbours, so a value is new exactly when it differs from the element before it.

That suggests a cleaner technique that needs no second array. Walk through the sorted array with an index i and keep a second index p that marks where the last distinct value was placed. Every time arr(i) is new, move p one step right and copy arr(i) there. The distinct values pile up at the front of the array, in ascending order, and the first p + 1 elements are the answer. The sort costs O(n log n) and the pass costs O(n).

Here is the idea on [1, 1, 2, 3, 3], which is already sorted. Initially p = 0. At i = 2 the value 2 differs from 1, so p becomes 1 and arr(1) is set to 2. At i = 3, the value 3 differs from 2, so p becomes 2 and arr(2) is set to 3. At i = 4 the value 3 equals its predecessor and nothing happens. The array is now [1, 2, 3, 3, 3] and the first p + 1 = 3 elements, [1, 2, 3], are the result.

Step by step

Make a sorted copy. val arr = nums.sorted puts equal values next to each other. Everything after this works on arr.
Declare p as a var set to 0. It is the index where the last distinct value sits. The first element is always kept, so index 0 is already correct.
Loop over the rest. 1 until arr.length starts at the second element, so each element has a predecessor to compare with.
Test for a new value. If arr(i) differs from arr(i - 1), this value appears for the first time.
Record it. Increase p by 1, then copy arr(i) to arr(p), right after the distinct values found so far.
Return the prefix. arr.slice(0, p + 1) holds the p + 1 distinct values. Being the last expression, it is the method's result.

The solution in Scala

class Solution {

    def removeDuplicates(nums: Array[Int]): Array[Int] = {
        val arr = nums.sorted
        var p = 0
        for (i <- 1 until arr.length) {
            if (arr(i) != arr(i - 1)) {
                p += 1
                arr(p) = arr(i)
            }
        }
        arr.slice(0, p + 1)
    }
}

The Scala details worth knowing:

val with a mutable array. arr is a val, so the name can't be reassigned, but the array's elements can still be changed. The line arr(p) = arr(i) is legal for that reason.
Assignment into an array uses parentheses too. arr(p) = value is how Scala writes what other languages write as arr[p] = value.
Writing while reading is safe. The write position p is never ahead of the read position i, so a write never destroys a value the loop still has to look at. In particular arr(i - 1) is only ever overwritten with its own value.
No ++ in Scala. Use p += 1.
slice(0, p + 1) excludes its end. That is why it is p + 1, not p. The result is a new array, so the method returns an array of the right length, not the old one with junk at the end.
The input is not modified. sorted returns a copy, so the caller's nums keeps its order.

Complexity

Time: O(n log n). Sorting is O(n log n), the loop is a single O(n) pass, and the final slice copies at most n elements.

Space: O(n) in this version, because sorted makes a copy of the input and slice makes another. The compacting idea itself needs only two indices. Sorting nums in place with scala.util.Sorting.quickSort would reduce the extra memory to the returned slice, at the price of changing the caller's array.

Edge cases and common mistakes

Empty array. The loop doesn't run, and slice(0, 1) of an empty array is an empty array. The result is empty without an exception.
One element. [7] returns [7].
All values equal. [5, 5, 5] never moves p, and the result is [5].
Returning the whole array. After compacting, the tail still holds leftover values. Without the slice, [1, 1, 2, 3, 3] would return [1, 2, 3, 3, 3].
Slicing to p. This drops the last distinct value.
Skipping the sort. The neighbour comparison only finds duplicates that are adjacent. On the unsorted [1, 2, 1] it would keep both 1s.
Negative numbers. They sort before zero and need no special handling. For the example input the result is [-2, 1, 2, 3, 4].

Testing

[2, 3, 1, 1, 4, 3, -2, 1] gives [-2, 1, 2, 3, 4], which is the five distinct values in ascending order.
[7] gives [7].
[] gives [].
[5, 5, 5] gives [5].

Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free