Start learning free

LESSON 200 OF 347 · SORTING

Distinct Values in C#: O(n log n) with Array.Sort

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

    C# · SORTING

    Distinct Values in C#, explained

    Problem overview

    The method DistinctValues receives an int[] and returns how many different values it contains. For [1, 5, -3, 1, -4, 2, -4, 7, 7] the answer is 6, because the distinct values are 1, 5, -3, -4, 2 and 7. The array has nine elements, but 1, -4 and 7 each appear twice.

    Approach: sort so that duplicates become neighbours

    Comparing every element with every other one works but costs O(n²). The lesson allows O(n log n) time, which points to sorting first.

    After sorting, equal values sit next to each other. The example becomes [-4, -4, -3, 1, 1, 2, 5, 7, 7]. Now a value is new exactly when it differs from the element just before it, so one pass over the array is enough. The sort costs O(n log n) and the pass costs O(n).

    The count starts at 1, not 0. The first element is always the first time its value is seen, so it counts automatically, and the loop only has to look at the elements after it.

    Tracing the sorted example: the counter starts at 1 for the first -4. The second -4 equals its neighbour, so nothing changes. Then -3, 1, 2, 5 and 7 each differ from the element before them and raise the counter to 6, while the repeated 1 and the repeated 7 are skipped. The final value is 6.

    Step by step

    1. Sort the array. Array.Sort(nums) sorts in place, ascending, and returns nothing.
    2. Start the counter at 1. The variable distinct holds the number of distinct values found so far, and the first element is the first one.
    3. Loop from index 1. Each element is compared with the one before it, so the loop starts at the second element and runs while i < nums.Length. For an array, Length is a property: no parentheses.
    4. Compare with the previous element. If nums[i] != nums[i - 1], the value is new, and distinct++ adds one. Equal neighbours are duplicates and change nothing.
    5. Return the counter once the loop is done.

    The solution in C#

    class Solution {
    public int DistinctValues(int[] nums) {
        Array.Sort(nums);
        int distinct = 1;
        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] != nums[i - 1]) {
                distinct++;
            }
        }
        return distinct;
    }
}

    A few C# notes:

    • The array is modified. Array.Sort reorders the caller's array. The count is correct, but the original order is gone.
    • Integer comparison needs no special care. != on int values compares the numbers, so -4 != -4 is false and two equal values are never counted twice.
    • distinct++ adds one to the variable. Used as a standalone statement, it means the same as distinct += 1.

    Complexity

    Time: O(n log n). The sort dominates. The loop visits each element once, which is O(n).

    Space: O(1) extra. The array is sorted in place and the method keeps only the counter and the loop index.

    Edge cases and common mistakes

    • A single element. The loop doesn't run, and the method returns 1, which is right.
    • All elements equal. [4, 4, 4] never increases the counter, so the answer is 1.
    • No duplicates. [3, 1, 2] gives 3, because every comparison between neighbours finds a difference.
    • An empty array. The method would return 1, although the right count is 0. The lesson's tests have non-empty arrays, but if you reuse this code, add a check at the top: if (nums.Length == 0) return 0;.
    • Counting without sorting. Comparing only neighbours in an unsorted array misses duplicates that are far apart. In [1, 2, 1] every neighbouring pair differs, so the loop would report 3 instead of 2.
    • Starting the loop at 0. nums[i - 1] would then read index -1 and throw IndexOutOfRangeException.

    Testing

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