Return k smallest elements using heap
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an unsorted array nums of up to 1,000,000 integers and an integer k (1 <= k <= nums.length), return the k smallest elements in ascending order.
Design an algorithm that runs in O(n log k) time and uses O(k) extra space via a heap. Clarify handling of duplicates and negative numbers; stable ordering among equal values is not required.
Follow-up: streaming version where numbers arrive online and you must support getSmallestK() at any time.
Quick Answer: This question evaluates proficiency with heap-based data structures, efficient algorithm design and complexity analysis for large inputs (O(n log k)) while reasoning about edge cases such as duplicates and negative values, and it falls under the Coding & Algorithms domain.
Given an unsorted array `nums` of up to 1,000,000 integers and an integer `k` (1 <= k <= nums.length), return the `k` smallest elements in ascending order.
Design an algorithm that runs in O(n log k) time and uses O(k) extra space via a heap. Handle duplicates and negative numbers correctly. Stable ordering among equal values is not required — only the multiset of returned values and their ascending order matter.
Example: for `nums = [7, 10, 4, 3, 20, 15]` and `k = 4`, return `[3, 4, 7, 10]`.
The canonical heap approach maintains a max-heap of size k while scanning the array: push the first k elements, then for each remaining element, if it is smaller than the current heap maximum, replace the max. At the end the heap holds the k smallest elements, which you sort ascending before returning.
Constraints
- 1 <= nums.length <= 1,000,000
- 1 <= k <= nums.length
- Elements may be negative, zero, or positive
- Duplicates are allowed and must be preserved in the output multiset
- Stable ordering among equal values is not required
Examples
Input: ([3, 1, 2, 4, 5], 3)
Expected Output: [1, 2, 3]
Explanation: The three smallest values are 1, 2, 3, returned in ascending order.
Input: ([7, 10, 4, 3, 20, 15], 4)
Expected Output: [3, 4, 7, 10]
Explanation: The four smallest values out of the six are 3, 4, 7, 10.
Hints
- Sorting the whole array is O(n log n). To hit O(n log k), avoid touching all elements with a full sort — keep only the k candidates you care about.
- Use a max-heap of size k. The root is the largest of your current k smallest. When a new element is smaller than the root, it deserves a spot, so pop the root and push the new element.
- Python's heapq is a min-heap; simulate a max-heap by negating values on the way in and negating again on the way out.
- After the scan, the heap contains exactly the k smallest elements in no particular order — sort them ascending (O(k log k)) before returning.
- For the streaming follow-up, keep the same size-k max-heap as a running data structure: each incoming number does an O(log k) push/replace, and getSmallestK() returns the sorted heap contents in O(k log k).