Kth Largest Element in a Stream
EasyThe problem
Build a KthLargest that is created with k and a starting list nums. Each call to Add(val) puts a new number into the stream and returns the k-th largest number seen so far (counting duplicates).
- Example 1Input: Constructor(3, [4, 5, 8, 2]) Add(3) Add(5) Add(10) Add(9) Add(4)Output: 4, 5, 5, 8, 8
After Add(3) the numbers are 2, 3, 4, 5, 8, so the 3rd largest is 4. After Add(5) it is 5. After Add(10) the top three are 10, 8, 5, giving 5. After Add(9) they are 10, 9, 8, giving 8. Add(4) changes nothing, so 8.
- 1 ≤ k ≤ 10,000
- 0 ≤ nums.length ≤ 10,000
- Up to 10,000 calls to Add
- There are always at least k numbers when Add is called
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
You only ever care about the k biggest numbers. Which of them is the "weakest"?
The idea
Min-heap of size k. Push each new number; if size exceeds k pop the smallest. The top is the k-th largest.
Target: O(log k) per add
Go function shape
type KthLargest struct{}
func Constructor(k int, nums []int) KthLargest
func (k *KthLargest) Add(val int) intReference solution
Tested with go test. Try it yourself first, then compare.
// KthLargest keeps a MIN-heap of the k largest numbers seen. Its root is the smallest of those k,
// which is exactly the k-th largest overall.
type KthLargest struct {
k int
h *minInts
}
type minInts []int
func (h minInts) Len() int { return len(h) }
func (h minInts) Less(i, j int) bool { return h[i] < h[j] }
func (h minInts) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *minInts) Push(x any) { *h = append(*h, x.(int)) }
func (h *minInts) Pop() any {
old := *h
x := old[len(old)-1]
*h = old[:len(old)-1]
return x
}
func NewKthLargest(k int, nums []int) *KthLargest {
kl := &KthLargest{k: k, h: &minInts{}}
for _, n := range nums {
kl.Add(n)
}
return kl
}
func (kl *KthLargest) Add(val int) int {
heap.Push(kl.h, val)
if kl.h.Len() > kl.k {
heap.Pop(kl.h) // the smallest can no longer be in the top k
}
return (*kl.h)[0]
}