Start learning free

LESSON 201 OF 338 · SORTING

Distinct Values in Go: O(n log n) by Sorting First

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

    GO · SORTING

    Distinct Values in Go, explained

    Problem overview

    The function distinctValues receives a slice of integers, nums, and returns how many different values it contains. Repeated values count once.

    In the example, nums = [1, 5, -3, 1, -4, 2, -4, 7, 7]. The different values are 1, 5, -3, -4, 2 and 7, so the answer is 6, even though the slice holds nine elements.

    The lesson asks for O(n log n) time and O(1) extra space, which rules out a map of values seen so far (that would use O(n) space) and also rules out comparing every pair of elements (O(n²) time).

    Approach: sort so that duplicates become neighbours

    In an unsorted slice, a repeated value can sit anywhere, and finding it means looking at many other elements. After sorting, all equal values form one block. A value is then new exactly when it differs from the element just before it. So one pass over the sorted slice, comparing each element with its left neighbour, counts the blocks, and the number of blocks is the number of distinct values.

    On the example, the sorted slice is [-4, -4, -3, 1, 1, 2, 5, 7, 7]. The blocks are -4 -4, -3, 1 1, 2, 5 and 7 7: six of them.

    Step by step

    1. Sort in place. sort.Ints(nums) reorders the slice ascending and returns nothing, so equal values end up side by side.
    2. Start the counter at 1. distinct := 1 declares and initialises the variable. The first element always begins a block, so it counts as a new value before the loop looks at anything.
    3. Loop from the second element. Go has a single loop keyword, for, and the three-part form for i := 1; i < len(nums); i++ looks like the C-style loop without parentheses. Starting at 1 lets nums[i-1] exist on every pass.
    4. Compare with the previous element. If nums[i] != nums[i-1], a new block starts here, so increment distinct. Because the slice is sorted, comparing with the neighbour is enough. A value can't reappear later after a different one.
    5. Return the counter once the loop ends.

    The solution in Go

    func distinctValues(nums []int) int {
    sort.Ints(nums)
    distinct := 1
    for i := 1; i < len(nums); i++ {
        if nums[i] != nums[i-1] {
            distinct++
        }
    }
    return distinct
}

    A few Go details are worth knowing here:

    • distinct++ is a statement, not an expression. You can write it on its own line, but not inside another expression such as x := distinct++.
    • The file needs import "sort", and Go rejects an unused import, so the import and the call to sort.Ints go together.
    • A slice is passed as a small header (pointer, length, capacity) that points at the same array. That is why sort.Ints inside the function reorders the caller's data too. After the call on the example, the caller's nums reads [-4 -4 -3 1 1 2 5 7 7].

    Complexity

    Time: O(n log n). Sorting costs O(n log n), and the loop adds a single O(n) pass. The larger term wins.

    Space: O(1) extra. The sort works in place and the function only keeps two integers, distinct and i. The price is that the input is modified.

    Edge cases and common mistakes

    • One element. The loop body never runs and the function returns 1, which is correct.
    • All elements equal. [3, 3, 3] never triggers the if, so the answer is 1.
    • Negative numbers. They sort and compare like any other integers: [-1, 0, -1, 0] gives 2.
    • An empty slice. The solution returns 1, because the counter starts at 1 without checking the length. The correct answer for an empty input would be 0. If your inputs can be empty, add if len(nums) == 0 { return 0 } before the sort.
    • Forgetting to sort. Without the sort, the neighbour comparison counts changes between adjacent values, not distinct values. For [1, 2, 1] that would give 3 instead of 2.
    • Starting the loop at 0. That reads nums[-1], and Go stops the program with an index-out-of-range panic.

    Small inputs to try in the editor above: [1, 5, -3, 1, -4, 2, -4, 7, 7] should give 6, [4] should give 1 and [-1, 0, -1, 0] should give 2.

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