Start learning free

LESSON 201 OF 348 · SORTING

Distinct Values in Kotlin: O(n log n) by 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 value nums[i] has not been seen before. How can we check this?

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

STEP 1 OF 5
    Ctrl + Enter to check

    KOTLIN · SORTING

    Distinct Values in Kotlin, explained

    Problem overview

    Given an IntArray named nums, distinctValues 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. The values 1, -4 and 7 each appear twice but are counted once.

    Approach

    The brute-force idea is to compare every element with every earlier one and count it only if it is new. That takes O(n^2) time. A hash set would make it linear, but it needs extra memory, and the lesson asks for O(n log n) time with O(1) extra space.

    Sorting gives a cheap test for "have I seen this before?". After sorting, equal values sit next to each other, so a value is new exactly when it differs from the element just before it. One comparison with the neighbour replaces the comparison with everything seen earlier.

    Sorted, the example becomes [-4, -4, -3, 1, 1, 2, 5, 7, 7]. Counting the places where a value differs from its left neighbour gives -3, 1, 2, 5 and 7, which is 5 changes. Add the first element, which is always new, and the total is 6.

    Step by step

    1. Sort in place. nums.sort() rearranges the array itself. Using sorted() would build a new list and leave nums in its original order, which defeats the purpose.
    2. Start the counter at 1. distinct is a var because it changes. The first element is always a new value, so the count begins at 1.
    3. Loop from the second element. for (i in 1 until nums.size) visits indices 1 to nums.size - 1. Starting at 1 means nums[i - 1] always exists.
    4. Compare with the previous element. If nums[i] != nums[i - 1], a new run of equal values starts here, so increment distinct.
    5. Return the count.

    The solution in Kotlin

    class Solution {
    fun distinctValues(nums: IntArray): Int {
        nums.sort()
        var distinct = 1
        for (i in 1 until nums.size) {
            if (nums[i] != nums[i - 1]) {
                distinct++
            }
        }
        return distinct
    }
}

    Kotlin details worth knowing:

    • 1 until nums.size is a range that excludes its end. The similar-looking 1..nums.size includes the end, so it would read nums[nums.size] and throw an ArrayIndexOutOfBoundsException.
    • When the range is empty, as with a one-element array (1 until 1), the loop body never runs and the answer stays 1.
    • != on Int compares values. It is the opposite of ==.
    • distinct++ is a statement here. Kotlin doesn't need a semicolon at the end of a line.
    • The function sorts the caller's array. After the call, the array passed in is in ascending order.

    Complexity

    • Time: O(n log n) for the sort and O(n) for the single pass. The sort dominates.
    • Space: O(1) extra, since the array is sorted in place and only two variables are added.

    Edge cases and common mistakes

    • Empty array. This version returns 1, because it assumes a first element exists. On an empty IntArray the loop doesn't run, so the starting value 1 comes back even though the true answer is 0. The lesson's inputs have at least one value; if yours might not, return 0 first when nums.isEmpty().
    • Skipping the sort. Without it, [1, 2, 1] would count 3, since each element differs from its neighbour.
    • Starting the counter at 0. The first element would then never be counted, giving a result one too small.
    • Starting the loop at 0. nums[-1] throws an ArrayIndexOutOfBoundsException.
    • All equal. [4, 4, 4] never triggers the if, so the answer is 1.

    Testing

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