Description
Maintain the kth largest value as integers arrive, counting duplicates separately. Constructor inputs are k and the initial values; add returns the kth largest after insertion. Queries occur only after at least k values exist.
Solution
import heapq
def create_kth_largest(k, nums):
state = {"k": k, "heap": []}
for value in nums:
add(state, value)
return state
def add(state, value):
heap = state["heap"]
heapq.heappush(heap, value)
if len(heap) > state["k"]:
heapq.heappop(heap)
return heap[0]Examples
Example 1
- Input
[["KthLargest",3,[4,5,8,2]],["add",3],["add",5],["add",10]]- Output
[null,4,5,5]
The top three change as values arrive.
Example 2
- Input
[["KthLargest",1,[]],["add",-3],["add",-2]]- Output
[null,-3,-2]
For k = 1, return the running maximum.
Example 3
- Input
[["KthLargest",2,[2,2]],["add",2]]- Output
[null,2]
Duplicates occupy separate ranks.
Approach
Keep a min-heap containing at most the k largest values seen. Insert each new value and remove the minimum if the heap grows beyond k. Its root is then the kth largest.
Time & space
O(n log(k + 1)) constructor time, O(log(k + 1)) per add, and O(k) auxiliary space; n is the initial count.