Katkat
Back

Return the K Smallest Integers

Hudson River TradingSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Implement an algorithm to extract the k smallest integers from an unsorted list in ascending order, preserving duplicates, and analyze the trade-offs between sorting, heaps, quickselect, and bounded-range approaches.

Problem Statement

Given an unsorted list of integers nums and an integer k, return the k smallest integers from nums in ascending order. If there are duplicate values, preserve their occurrences as long as they fall within the k smallest elements.

Be prepared to discuss and compare multiple implementations (full sorting, max-heap of size k, quickselect partitioning, and counting/bucket approaches) with respect to time complexity, auxiliary memory, worst-case bounds, and suitability for streaming data.

Function Signature

def k_smallest(nums: list[int], k: int) -> list[int]:
    pass

Input and Output Format

  • Input:
    • nums: A list of integers (can be positive, negative, or zero; may contain duplicates).
    • k: A non-negative integer representing the number of smallest elements to return.
  • Output: A list of k integers sorted in ascending order.

Constraints

  • 0 <= k <= len(nums) <= 1,000,000
  • -10^9 <= nums[i] <= 10^9

Examples

Example 1

Input: nums = [7, 10, 4, 3, 20, 15], k = 3
Output: [3, 4, 7]
Explanation: The 3 smallest elements are 3, 4, and 7.

Example 2

Input: nums = [5, 2, 2, 8, 1, 5], k = 4
Output: [1, 2, 2, 5]
Explanation: Preserves the duplicated value 2 since both occurrences are among the 4 smallest elements.

Edge Cases

  • k == 0: Should return an empty list [].
  • k == len(nums): Should return the entire array sorted.
  • nums contains identical elements (e.g., [4, 4, 4, 4], k = 2 -> [4, 4]).
  • nums contains negative numbers.

Hints

Hint 1

If k is much smaller than the array size N, maintaining a max-heap of size k avoids sorting the entire array and requires only O(k) extra space.

Hint 2

Quickselect can find the k-th smallest element and partition the array in O(N) average time, after which you only need to sort the first k elements in O(k log k).

Hint 3

Consider the worst-case behavior: standard Quickselect degrades to O(N^2) on adversarial inputs, whereas a heap approach guarantees O(N log k) time.

Follow-up questions

  • How would you adapt your solution if the input arrives as a continuous, unbounded data stream and memory is strictly limited to O(k)?
  • If nums[i] is guaranteed to be within a tight range like [0, 10^5], how can you optimize the time complexity to O(N + range)?
  • If the array is immutable and k_smallest is called millions of times with different values of k, what preprocessing would you perform?