# Return the K Smallest Integers Given an unsorted list of integers and an integer `k`, return the `k` smallest values in ascending order. Preserve duplicate values. ```python def k_smallest(values: list[int], k: int) -> list[int]: ... ``` ## Examples ```text Input: values = [9, 1, 5, 3, 1, 8], k = 4 Output: [1, 1, 3, 5] Input: values = [4, 2], k = 0 Output: [] ``` ## Constraints and Errors - `0 <= len(values) <= 500_000` - `-10**18 <= values[i] <= 10**18` - `0 <= k <= len(values)` - A non-integer value or `k`, including a Boolean, or a `k` outside the valid range raises `ValueError`. - Validate all inputs before selecting values. - Do not mutate `values`. ## Required Discussion Before choosing an implementation, compare: - sorting the complete input; - maintaining a max-heap of size `k`; - quickselect followed by sorting only the selected prefix; and - counting or bucket methods when the value range is small. Explain how input size, `k`, memory, output ordering, repeated queries, and worst-case requirements affect the choice. ## Hints - A size-`k` max-heap takes `O(n log k)` time and `O(k)` selection space. - Quickselect partitions around a pivot and has expected `O(n)` selection time with a randomized or otherwise well-behaved pivot strategy. - Repeatedly choosing an extreme pivot creates subproblems of sizes `n - 1`, `n - 2`, and so on, yielding `O(n**2)` worst-case work. - Because the required output is sorted, account for the final `O(k log k)` ordering step when using selection.