HardPro challengePythonJavaScriptTypeScript
K Largest Elements
Data StructuresHeapAlgorithms
Implement a MinHeap from scratch and use it to extract the k largest
numbers from an unsorted array in O(n log k) time.
MinHeap contract
push(val) — insert a value and restore the heap invariant
pop() — remove and return the minimum; null if empty
peek() — return the minimum without removing; null if empty
size — getter returning the current element countAlgorithm
Maintain a min-heap of exactly k elements. For each number in nums:
- If the heap has fewer than
kitems, push unconditionally. - Otherwise, if the number exceeds the current minimum (
peek()), pop
the minimum and push the new number.
After processing all numbers, drain the heap and return the results sorted
in descending order.
Examples
solve([3, 1, 5, 12, 2, 11], 3) → [12, 11, 5]
solve([7, 7, 7, 7], 2) → [7, 7]
solve([-4, -1, -7, -3], 2) → [-1, -3]Constraints
1 ≤ k ≤ nums.length- Values may be negative or duplicate.
- You must implement the heap manually (no
Array.prototype.sorton the
full array — that would be O(n log n) and misses the point).
Sample tests
Test #1Three largest from a mixed array
Input: [[3,1,5,12,2,11],3]
Output: [12,11,5]
Test #2All equal values — k duplicates returned
Input: [[7,7,7,7],2]
Output: [7,7]
Test #3Negative numbers — largest means closest to zero
Input: [[-4,-1,-7,-3],2]
Output: [-1,-3]