Start learning free

LESSON 199 OF 347 · SORTING

Smallest K in C#: O(n log n) with Array.Sort and Take

Practice O(n log n) Read the full explanation

Given an array of positive integers nums, return the smallest k values, in any order you want.

Example:

Input: nums = [5, 9, 3, 6, 2, 1, 3, 2, 7, 5], k = 4
Output: [1, 2, 2, 3]
Explanation: Smallest number is 1, 2nd smallest is 2, 
            3rd smallest is 2, 4th smallest is 3

The result can be in any order, [2, 1, 3, 2] is also a correct answer.

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)


STEP 1 OF 2
    Ctrl + Enter to check

    C# · SORTING

    Smallest K in C#, explained

    Problem overview

    The method KSmallest receives an int[] called nums and a count k. It must return the k smallest values as a new int[]. The order of the result doesn't matter, so for nums = [5, 9, 3, 6, 2, 1, 3, 2, 7, 5] and k = 4, both [1, 2, 2, 3] and [2, 1, 3, 2] are correct.

    Duplicates count separately. The array holds the value 2 twice, and the answer contains it twice, because the 2nd and 3rd smallest elements are both 2.

    Approach: sort, then take the front

    If the array is sorted in ascending order, the smallest values are simply its first k elements. That reduces the problem to two operations: sort, then copy a prefix.

    The statement asks for O(n log n) time, which is exactly the cost of a comparison sort. Copying the first k elements costs O(k), and k is at most n, so the sort dominates. Faster approaches exist, such as a heap or a partition-based selection, but this lesson uses the simplest idea.

    Here is the idea on the example. After sorting, nums is [1, 2, 2, 3, 3, 5, 5, 6, 7, 9]. The first four elements are 1, 2, 2, 3, which is the expected answer.

    Step by step

    1. Sort in place. Array.Sort(nums) reorders the array itself and returns nothing. For an int[] it sorts in ascending order, so no comparer is needed.
    2. Return the first k elements. nums.Take(k) describes "the first k elements", and ToArray() copies them into the int[] that the method promises to return.

    The solution in C#

    class Solution {
    public int[] KSmallest(int[] nums, int k) {
        Array.Sort(nums);
        return nums.Take(k).ToArray();
    }
}

    The C# details worth knowing:

    • Take comes from LINQ. It is an extension method in System.Linq, so a program that uses it needs using System.Linq;. Array.Sort lives in System.
    • Take is lazy. It doesn't copy anything by itself. It produces the elements one by one when something asks for them, and ToArray() is the call that asks for all of them and stores them in a new array.
    • The input array changes. Array.Sort sorts nums in place, so the caller's array is sorted after the call. If the original order matters elsewhere, sort a copy instead.
    • Take is forgiving about k. If k is larger than the array, Take returns all the elements instead of throwing. If k is 0 or negative, it returns an empty sequence.
    • Sorting is not stable for equal values, and it doesn't need to be. Equal integers are indistinguishable, so the result is the same whichever copy of a value comes first.

    Complexity

    Time: O(n log n). Array.Sort is a comparison sort, so it costs O(n log n). Taking the first k elements is O(k), which never exceeds O(n).

    Space: the sort works inside the input array and needs no second array. The only allocation of note is the returned array of k elements, which the method has to produce anyway.

    Edge cases and common mistakes

    • Duplicates. Don't remove them. For [2, 2, 1] and k = 2, the answer is [1, 2], and for [2, 2, 2] and k = 2 it is [2, 2].
    • k equal to the length. The result is the whole array, sorted.
    • k larger than the length. Take returns every element rather than failing. A hand-written loop that copies k elements would throw IndexOutOfRangeException instead.
    • Forgetting ToArray(). Take(k) returns an IEnumerable<int>, not an int[], so returning it directly doesn't compile.
    • Taking the wrong end. After an ascending sort the smallest values are at the front. Taking from the back would give the largest.

    Testing

    • nums = [5, 9, 3, 6, 2, 1, 3, 2, 7, 5], k = 4 gives [1, 2, 2, 3].
    • nums = [5, 9, 3], k = 10 gives [3, 5, 9].
    • nums = [5, 9, 3], k = 0 gives [].
    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