K Smallest

Return the k smallest elements of the array, sorted ascending. Assume 0 <= k <= len(nums).

kSmallest(nums, k)

Input format: nums | k. Output the k smallest values, sorted, space-separated.

Examples

[5, 2, 8, 1, 9], k=3   // → [1, 2, 5]
[4, 3], k=0            // → []
[7], k=1               // → [7]

Walkthrough

Thinking it through

The simplest approach: sort ascending, take the first k. Works, but like finding a single k-th ranked element, full sorting spends effort ordering elements far outside the k smallest — effort you don't need.

Reframing the problem

You only need to know which k elements are smallest, and their order among themselves — not the exact order of everything. That suggests tracking a bounded set of candidates instead of fully sorting.

The heap-based approach

Maintain a max-heap of size k — root is always the largest of the tracked values. Backwards-feeling, but symmetric to the k-largest problem:

Feed elements into the max-heap.
Once it holds k elements, its root is the largest of your current k-smallest candidates.
For each new element: smaller than the root means it belongs more than the current worst candidate — evict the root, insert the new one. Otherwise, skip it.
After the scan, the heap holds exactly the k smallest. Sort the small k-sized result to present ascending.

The max-heap tracks "who's the weakest candidate I'd throw out if something better shows up" — the largest of the tracked values, hence a max-heap even though the target is the smallest elements overall.

Why this beats full sorting

Each heap operation costs O(log k), across n elements giving O(n log k) — cheaper than O(n log n) whenever k is small relative to n.

The trade-off

The heap tracks only k elements — O(k) space instead of a fully sorted O(n) array — but gives no information about anything outside those k. Since the problem only asks for the k smallest, that's exactly the information you don't need.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.