Start learning free

LESSON 200 OF 348 · SORTING

Smallest K Integers in TypeScript: 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

    TYPESCRIPT · SORTING

    Smallest K in TypeScript, explained

    Problem overview

    The method kSmallest receives an array of positive integers, nums, and a number k. It returns the k smallest values, in any order.

    In the example, nums = [5, 9, 3, 6, 2, 1, 3, 2, 7, 5] and k = 4. Written in ascending order, the array is [1, 2, 2, 3, 3, 5, 5, 6, 7, 9], so the four smallest values are 1, 2, 2 and 3. Duplicates count separately: the second 2 is the third smallest value, so it belongs in the answer.

    The statement sets a budget of O(n log n) time and O(1) extra space. There are faster approaches, but this lesson uses the simplest one.

    Approach: sort, then take a prefix

    Once an array is sorted in ascending order, the smallest values are at the front. The k smallest are simply the first k elements. So the whole problem splits into two steps: sort, then cut off a prefix.

    Sorting costs O(n log n), which matches the budget. Taking the prefix costs O(k), and k can't be more than n, so the sort dominates. The alternative is to pick the minimum k times, which takes O(n * k) and gets slow when k is large.

    Step by step

    1. Sort nums in place with a comparator that returns a - b. A negative result puts a first, so subtracting gives ascending order. The comparator is required: without it, sort compares the numbers as strings and puts 10 before 9.
    2. Return the first k elements with slice(0, k). It copies the elements from index 0 up to, but not including, index k, which is exactly k elements.

    The solution in TypeScript

    class Solution {
    kSmallest(nums: number[], k: number): number[] {
        nums.sort((a, b) => a - b);
        return nums.slice(0, k);
    }
}

    Details worth knowing:

    • The comparator. The types number[] let TypeScript infer that a and b are numbers. Types are erased when the code compiles to JavaScript, so they don't change how sort runs. Leaving the comparator out still compiles, and gives the wrong order for numbers of different lengths: [10, 9, 100].sort() gives [10, 100, 9].
    • sort changes the caller's array. After kSmallest(nums, 4), the array that was passed in is sorted. That is what makes the extra space small. If the caller needs the original order, sort a copy with [...nums].sort(...), which costs O(n) extra space.
    • slice returns a new array and leaves the array it is called on unchanged. The result is separate from nums.
    • The end index is exclusive. slice(0, 4) returns the elements at indices 0, 1, 2 and 3.

    Complexity

    Time: O(n log n). Sorting n numbers takes O(n log n) comparisons, each constant time. The slice copies at most n elements.

    Space: O(1) beyond the output. The sort happens in place, so no second copy of the input is made by this code. The array returned by slice is the answer itself, and the lesson doesn't count it.

    Edge cases and common mistakes

    • k equal to 0. slice(0, 0) returns an empty array.
    • k larger than the array length. slice stops at the end, so kSmallest([4, 1], 5) returns [1, 4], all the elements.
    • Forgetting the comparator. With [10, 9, 100] and k = 2, the string order makes the answer [10, 100] instead of [9, 10].
    • Off by one in slice. slice(0, k - 1) returns one element too few, and slice(0, k + 1) one too many.
    • Using the return value of sort as a copy. sort returns the same array, not a new one.
    • Duplicates. Don't remove them first. For the example, the answer needs both 2s.

    Testing

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