LESSON 264 OF 414 · HASH TABLE

Distinct Values in Scala: O(n) with a Mutable Set

Given an array of integers, count how many distinct values exist in the array.

Example:

Input: [1, 5, -3, 1, -4, 2, -4, 7, 7]
Output: 6
Explanation: the distinct values in the array are [1, 5, -3, -4, 2, 7]

Note:

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

STEP 1 OF 6

Guided

Ctrl + Enter to check

SCALA · HASH TABLE

Distinct Values in Scala, explained

Problem overview

The method distinctValues receives an Array[Int] called nums and returns how many different values it contains. Repeats count once.

For Array(1, 5, -3, 1, -4, 2, -4, 7, 7) the distinct values are 1, 5, -3, -4, 2 and 7. That makes six, so the method returns 6. The array has nine elements, but 1, -4 and 7 each appear twice.

The lesson asks for O(n) time and O(n) extra space.

Approach: count a value the first time you see it

One way to count distinct values is to sort the array and count the places where a value differs from its neighbour. That takes O(n log n) time. This lesson trades memory for speed instead: it remembers every value seen so far in a hash set.

A hash set answers "is this value already in here?" in constant time on average. So the loop visits each number once. If the number is not in the set, it is new: put it in the set and add one to the count. If it is already there, skip it. After the last element, the count equals the number of distinct values, which is also the size of the set.

On the example, the loop counts 1, 5, -3 for the first three elements. The second 1 is already in the set, so it is skipped. Then -4 and 2 are counted, the second -4 is skipped, 7 is counted, and the second 7 is skipped. The final count is 6.

Why not compare every pair?

The simplest alternative is a nested loop that, for each element, scans the elements before it to see whether the value already appeared. That works, but each scan can be as long as the array, so the total is O(n²): ten thousand numbers could mean about fifty million comparisons. The set replaces each scan with a single lookup, and that is the whole gain of the lesson. The same "have I seen this?" pattern appears in many hash table problems.

Step by step

Create an empty mutable set of Int named values. Scala's default Set is immutable and can't be added to in place, so the lesson spells out scala.collection.mutable.Set[Int](). It is a val because the variable never points elsewhere, only the contents change.
Create the counter answer with var, starting at 0. It changes inside the loop, so val would not work.
Loop over the numbers with for (value <- nums). The order doesn't matter for counting.
Test for a new value with !values.contains(value). Only a number seen for the first time should be counted.
Record it. Inside the if, call values.add(value) so later copies are recognised, and write answer += 1. Scala has no ++ operator, so += 1 is the way to increment.
Return answer once the loop ends.

The solution in Scala

class Solution {
    def distinctValues(nums: Array[Int]): Int = {
        val values = scala.collection.mutable.Set[Int]()
        var answer = 0
        for (value <- nums) {
            if (!values.contains(value)) {
                values.add(value)
                answer += 1
            }
        }
        return answer
    }
}

The Scala details worth a closer look:

add returns a Boolean. For a mutable set, values.add(value) returns true when the value was new and false when it was already there. The solution ignores that result and checks with contains first, which makes each step explicit.
val with a mutable set. val values means the name always refers to the same set. The set's contents still change through add.
Which set you get. Writing Set[Int]() without the package gives an immutable set, which has no add method. The full name scala.collection.mutable.Set selects the mutable one.
The shorter form. Because the size of the set is the answer, nums.toSet.size gives the same result in one line. The lesson builds it by hand to practise the set operations and counter.
return is optional. The last expression of a Scala method is its value, so the final line could be just answer. The explicit return also works here, because it sits directly in the method body and not inside a for loop.

Complexity

Time: O(n). The loop runs n times. Each iteration does one contains and at most one add, each constant time on average.

Space: O(n). When all values are different, the set holds n entries. The sorting approach could use O(1) extra space, but it needs O(n log n) time and rearranges the array.

Edge cases and common mistakes

Empty array. The loop never runs and the method returns 0.
All values equal. Array(4, 4, 4) gives 1.
All values different. Array(1, 2, 3) gives 3.
Negative numbers and zero. They are ordinary keys. Array(0, -1, 0) gives 2.
Counting without the check. Writing answer += 1 for every element returns the array's length, not the number of distinct values.
Forgetting to add the value. If values.add(value) is missing, no number is ever found in the set, so every element is counted.

Testing

Array(1, 5, -3, 1, -4, 2, -4, 7, 7) gives 6.
Array(4, 4, 4) gives 1.
Array(1, 2, 3) gives 3.
Array(0, -1, 0) gives 2.
Array() gives 0.

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

Start learning free