Start learning free

LESSON 219 OF 414 · BRUTE FORCE

Remove Duplicates from Array in Scala: O(n^2) with ArrayBuffer

Practice O(n2) Read the full explanation

Given an array of integers, return a new array containing only the unique values.

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:

For this lesson, your algorithm should run in O(n^2) time and use O(n) extra space.
(There are faster solutions which we will discuss in future lessons)


Hints:

Let's use an extra array uniqueValues and add the unique values from nums there. We can traverse the array nums from left to right. We should add the current element into uniqueValues only if that value has not been seen before. How can we check this?

The current element has never been seen before if it doesn't occur in uniqueValues.
STEP 1 OF 4
    Ctrl + Enter to check

    SCALA · BRUTE FORCE

    Remove Duplicates From Array in Scala, explained

    Problem overview

    The method removeDuplicates receives an Array[Int] named nums and returns a new array that holds each distinct value once. The order of the result doesn't matter for the task. For Array(2, 3, 1, 1, 4, 3, -2, 1) the distinct values are 2, 3, 1, 4 and -2, so a valid answer is Array(2, 3, 1, 4, -2).

    The statement asks for O(n^2) time and O(n) extra space, and notes that faster solutions come in later lessons.

    Approach: keep a list of values seen so far

    Walk through nums from left to right and keep a second collection of the unique values met so far. For each value, check whether the collection already contains it. If not, this is the first occurrence, so add it. If so, skip it.

    The check is the expensive part. Looking for a value in an unsorted collection means scanning it element by element, and the collection can grow up to n elements. Doing that scan once for each of the n values gives O(n^2) time. A hash set would make each check roughly constant, and that is the faster approach left for a later lesson.

    A side effect of this method is that the result keeps the order of first appearance, which is why the example gives 2, 3, 1, 4, -2.

    Step by step

    1. Create the buffer. Declare val uniqueValues as an empty scala.collection.mutable.ArrayBuffer[Int]. A Scala Array has a fixed size, and the number of unique values isn't known in advance, so a growable buffer is the right container. val only fixes which buffer the name refers to; the contents can still change.
    2. Loop over the values. The indices aren't needed, so write for (value <- nums). It walks the elements directly.
    3. Test and add. Inside the loop, check !uniqueValues.contains(value). If the value is new, append it with uniqueValues += value.
    4. Convert and return. After the loop, uniqueValues.toArray is the last expression. It copies the buffer into the Array[Int] that the method has to return, and the last expression of a method is its result.

    The solution in Scala

    class Solution {
    def removeDuplicates(nums: Array[Int]): Array[Int] = {
        val uniqueValues = scala.collection.mutable.ArrayBuffer[Int]()
        for (value <- nums) {
            if (!uniqueValues.contains(value)) {
                uniqueValues += value
            }
        }
        uniqueValues.toArray
    }
}

    Scala details:

    • Mutable and immutable collections. Scala's default List, Vector and Map never change; adding to them builds a new collection. ArrayBuffer lives in scala.collection.mutable and changes in place, so += adds to the same buffer. The full name is written out here, but import scala.collection.mutable.ArrayBuffer would let you write just ArrayBuffer[Int]().
    • contains is a linear scan. It compares the argument with the elements in order, using ==, and stops at the first match.
    • Array is fixed-size. Elements can be replaced but the length can't change, which is why the result is collected in a buffer first.
    • A new array comes back. toArray copies, so nums itself is left untouched.

    Complexity

    Time: O(n^2). The loop runs n times. Each contains call scans up to the current size of uniqueValues, which is at most n. In the worst case, when all values are different, the scans have lengths 0, 1, 2, ..., n - 1, about n^2 / 2 comparisons in all. Appending to the buffer is cheap on average, and toArray is O(n).

    Space: O(n). The buffer holds up to n values when there are no duplicates, and toArray makes a copy of the same size.

    Edge cases and common mistakes

    • Empty input. The loop doesn't run, and an empty array comes back.
    • No duplicates. The result is a copy of the input, in the same order.
    • All equal. Array(7, 7, 7) gives Array(7).
    • Negative numbers and zero. They are values like any other; -2 is kept once in the example.
    • Using an Array for the result. It can't grow, so there is no way to add the unique values one at a time.
    • Forgetting the !. Without the negation, the condition is true only for values already in the buffer, and since the buffer starts empty, nothing is ever added.
    • Returning the buffer. The return type is Array[Int], so the buffer has to be converted with toArray.
    • Printing the result. Printing an Array shows an object reference. Use mkString(", ") to see the values.

    Testing

    • Array(2, 3, 1, 1, 4, 3, -2, 1) gives Array(2, 3, 1, 4, -2).
    • Array(7, 7, 7) gives Array(7).
    • Array(1, 2, 3) gives Array(1, 2, 3).
    • Array() gives an empty array.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free