Start learning free

LESSON 200 OF 348 · SORTING

Smallest K in Kotlin: O(n log n) with Sorting

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

    KOTLIN · SORTING

    Smallest K in Kotlin, explained

    Problem overview

    You get an IntArray named nums and an integer k. The function kSmallest must return the k smallest values as a new IntArray. The order of the result doesn't matter.

    For nums = [5, 9, 3, 6, 2, 1, 3, 2, 7, 5] and k = 4, the sorted array is [1, 2, 2, 3, 3, 5, 5, 6, 7, 9]. Its first four values are 1, 2, 2, 3, so that is the answer. Duplicates count separately: the value 2 appears twice in the result because it appears twice in the input.

    Approach

    The direct way to find the smallest value is to scan the array. Finding the second smallest needs another scan, and so on, which costs O(n * k) and gets slow when k is large.

    Sorting removes the repeated scans. Once the array is in ascending order, the k smallest values are exactly the first k positions. The cost is one sort, O(n log n), plus copying k values. Sorting in place needs no extra array, which fits the lesson's note of O(n log n) time with O(1) extra space. The result array of size k is the output itself, not working memory. Faster ways exist, and the other lessons on this problem cover them.

    Why does a prefix of the sorted array work? Every value after position k - 1 is greater than or equal to the value at k - 1, so no value left out can be smaller than one we keep. When several values tie at the boundary, any of them is a valid choice, and the problem accepts any order, so there is nothing more to decide.

    Step by step

    1. Sort nums in place. Call nums.sort(). On an IntArray it rearranges the array itself and returns nothing. That is what we want. The similar-looking sorted() returns a new List<Int>, which is a different type from the IntArray the function must return.
    2. Copy the first k elements. copyOfRange(0, k) creates a new IntArray holding the indices 0 to k - 1. The end index is exclusive, so passing k gives exactly k values.

    The solution in Kotlin

    class Solution {
    fun kSmallest(nums: IntArray, k: Int): IntArray {
        nums.sort()
        return nums.copyOfRange(0, k)
    }
}

    Some Kotlin details to know:

    • Function parameters are read-only names, so you can't write nums = something. The contents of an IntArray can still change, which is why nums.sort() compiles. The caller's array is sorted too, because both refer to the same array.
    • copyOfRange returns a new array of the same type. Changing the result later doesn't touch nums.
    • If k is larger than nums.size, copyOfRange(0, k) throws an IndexOutOfBoundsException. The lesson's inputs keep k within the array.

    Remember that nums is changed as a side effect. If the caller still needs the original order, make a copy first with nums.copyOf() and sort the copy. That copy costs O(n) extra space, which is why the lesson's version sorts in place.

    Complexity

    • Time: O(n log n) for the sort, plus O(k) for the copy. Since k <= n, the sort dominates.
    • Space: O(1) extra beyond the returned array, because the sort works in place.

    Edge cases and common mistakes

    • Using sorted() instead of sort(). nums.sorted() gives a List<Int>, and calling copyOfRange on nums afterwards would copy the still-unsorted array, returning the wrong values.
    • Off-by-one in the end index. copyOfRange(0, k - 1) returns only k - 1 values.
    • Duplicates. Don't remove them. With [2, 2, 2] and k = 2 the answer is [2, 2].
    • k = 0. copyOfRange(0, 0) returns an empty array.
    • k = nums.size. The result is the whole sorted array.

    Testing

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