Start learning free

LESSON 224 OF 414 · SORTING

Distinct Values in Scala: O(n log n) with Sorting

Practice O(n log n) Read the full explanation

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:

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


Hints:

Let's sort the array in non-decreasing order. In this way all the equal elements will come one after another.

Then, we can traverse the sorted array from left to right using an index i. We should increment the solution if the value at index i has not been seen before. How can we check this?

The value at index i has never been seen before if it is different from the value at index i - 1.

STEP 1 OF 5
    Ctrl + Enter to check

    SCALA · SORTING

    Distinct Values in Scala, explained

    Problem overview

    The method distinctValues receives an array of integers and returns how many different values it contains. For [1, 5, -3, 1, -4, 2, -4, 7, 7] the distinct values are 1, 5, -3, -4, 2, 7, so the answer is 6.

    Approach: sort so that equal values are neighbours

    Checking whether each value has appeared before would mean comparing it with all earlier elements, which is O(n²). Sorting removes that work. In a sorted array, equal values sit next to each other, so a value is new exactly when it differs from the element just before it.

    That gives a one-pass count. Start with 1, since the first element is always a new value, and add 1 each time an element differs from its predecessor. The sort costs O(n log n), the pass costs O(n), and the total is O(n log n), as the statement asks. Faster ways to count distinct values come in later lessons.

    For the example, the sorted array is [-4, -4, -3, 1, 1, 2, 5, 7, 7]. The element changes at -3, 1, 2, 5 and 7, which makes 5 increments on top of the starting 1: 6 distinct values.

    Step by step

    1. Sort nums in place with scala.util.Sorting.quickSort, so equal values end up adjacent.
    2. Start the counter at 1. It is a var because it changes. The first element is always a new value.
    3. Loop from the second element. 1 until nums.length makes i run from 1 to the last index, so nums(i - 1) always exists.
    4. Compare with the previous element. When nums(i) differs from nums(i - 1), a new value starts here, so add 1 to the counter.
    5. Return the counter after the loop.

    The solution in Scala

    class Solution {
    def distinctValues(nums: Array[Int]): Int = {
        scala.util.Sorting.quickSort(nums)
        var distinct = 1
        for (i <- 1 until nums.length) {
            if (nums(i) != nums(i - 1)) {
                distinct += 1
            }
        }
        return distinct
    }
}

    The Scala details worth knowing:

    • quickSort sorts in place. It lives in scala.util.Sorting and rearranges the array it is given. That is why the extra space stays small, but it also means the caller's array is changed. nums.sorted would return a new array and leave nums alone, at the cost of a copy.
    • No ++ operator. Scala has no increment operator, so the counter grows with distinct += 1.
    • Parentheses for indexing. Elements are read as nums(i).
    • Ranges exclude their end with until. 1 until nums.length stops at the last valid index. 1 to nums.length would include nums.length and fail with an ArrayIndexOutOfBoundsException.
    • != compares values. For integers, and for strings, it asks whether the contents differ.
    • return is optional at the end of a method. Writing just distinct would return the same value.

    Complexity

    Time: O(n log n). The sort takes O(n log n) and the loop is a single O(n) pass, so the sort dominates.

    Space: about O(1) extra. The sort works inside the input array and the loop adds one counter. (The sort itself needs a small amount of working memory, which is far below a copy of the array.)

    Edge cases and common mistakes

    • All values equal. [4, 4, 4] gives 1: the comparison never finds a change.
    • All values different. [3, 1, 2] gives 3.
    • One element. The loop does not run and the answer is 1.
    • Empty array. The code as written returns 1, because the counter starts at 1 without checking the length. The lesson's inputs always have elements, but a version meant for general use would return 0 first when nums.length == 0.
    • Counting without sorting. Comparing only neighbours in an unsorted array gives the wrong answer. For [1, 2, 1] every neighbour differs, giving 3, but there are only 2 distinct values.
    • Starting the counter at 0. The first element would never be counted, and every answer would be one short.
    • Looping from 0. nums(i - 1) would read index -1 and throw an exception.

    Testing

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