Start learning free

LESSON 225 OF 415 · SORTING

Distinct Values in Swift: 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 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

    SWIFT · SORTING

    Distinct Values in Swift, 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 different values are 1, 5, -3, -4, 2 and 7, so the answer is 6.

    The statement sets a budget of O(n log n) time. Comparing every element with every other one takes O(n²), so the lesson uses a sorting idea instead.

    Approach: sort, then compare neighbours

    Once an array is sorted, equal values sit next to each other. A value is then new exactly when it differs from the element just before it, and counting the distinct values becomes a single pass.

    Take the example. Sorted, it is [-4, -4, -3, 1, 1, 2, 5, 7, 7]. Reading from left to right, the second -4 equals its predecessor, so it adds nothing. -3 differs from -4, so it is new. The second 1 repeats, 2 is new, 5 is new, 7 is new and its repeat is not. Together with the first element, that makes 6.

    Step by step

    1. Sort the array in place. The parameter is declared inout, which lets the method change the caller's array, so nums.sort() is allowed.
    2. Start the count at 1. The first element is always a new value, because nothing comes before it. Declare the counter with var, since it changes.
    3. Loop from the second element. The range 1..<nums.count starts at index 1, so nums[i - 1] is always valid.
    4. Count each change. If nums[i] != nums[i - 1], a new value starts at position i, so add 1 with += 1. Swift has no ++.
    5. Return the count.

    The solution in Swift

    class Solution {
    func distinctValues(_ nums: inout [Int]) -> Int {
        nums.sort()
        var distinct = 1
        for i in 1..<nums.count {
            if nums[i] != nums[i - 1] {
                distinct += 1
            }
        }
        return distinct
    }
}

    The Swift details worth knowing:

    • inout parameters. The caller passes the array with an ampersand, as in solution.distinctValues(&values), and the method works on that variable. After the call, the caller's array is sorted. The caller must pass a var, not a let.
    • sort() compared with sorted(). sort() rearranges the array itself, which inout permits. A normal parameter is a constant, and there sorted() would be needed.
    • Half-open ranges. 1..<nums.count stops at the last index. For an array of one element the range is 1..<1, which is empty, so the loop doesn't run and the answer stays 1.
    • Empty arrays crash. For an empty array the range would be 1..<0. A range whose start is above its end is a run-time error in Swift, so the program stops. The lesson's inputs have at least one element, but a general-purpose version would check nums.isEmpty and return 0 first.
    • Comparing neighbours. != on two Int values compares their contents, so no special equality method is needed.

    Complexity

    Time: O(n log n). The sort costs O(n log n). The loop is one pass of O(n) and doesn't change the total.

    Space: The method creates no second array: it sorts the caller's array and keeps one counter. The sort may use some temporary memory of its own, but the method adds none to the data.

    Edge cases and common mistakes

    • One element. [9] returns 1.
    • All equal. [4, 4, 4] returns 1, since no neighbour differs.
    • All different. An array of five different values returns 5.
    • Forgetting to sort. Without sorting, equal values may be far apart, and comparing neighbours counts them more than once. In [1, 2, 1] every element differs from its neighbour, giving 3 where the answer is 2.
    • Starting the count at 0. The first element would never be counted, since the loop starts at index 1.
    • Looping from index 0. nums[-1] doesn't exist, and reading it crashes.
    • Side effect. Because of inout, the caller's array is left sorted. For [1, 5, -3, 1, -4, 2, -4, 7, 7] it becomes [-4, -4, -3, 1, 1, 2, 5, 7, 7].

    Testing

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