Top K Largest Values with a Heap
Meta● MediumFULLTIMEONSITE INTERVIEWProblem statement
Given an integer array nums and an integer k, return the k largest occurrences in nonincreasing order. Preserve duplicate occurrences.
Process the array with a min-heap containing at most k values, then order the selected values for the returned result. Return an empty array when k is zero.
Function
topKLargest(nums: int[], k: int) → int[]Examples
Example 1
nums = [3,2,1,5,6,4]k = 2return = [6,5]The size-two heap retains 5 and 6.
Example 2
nums = [4,1,4,2,4]k = 3return = [4,4,4]Duplicate occurrences remain separate selected values.
Example 3
nums = [-5,-1,-3]k = 0return = []Selecting zero values returns an empty result.
Constraints
0 <= nums.length <= 200000.-10^9 <= nums[i] <= 10^9.0 <= k <= nums.length.