Kth Largest Element in a Stream

Problem statement

Design a class that accepts a stream of integers and, after each Add, returns the kth largest value seen so far (not the kth distinct — duplicates count). On construction you’re given k and an initial list nums.

Example:

Input:

KthLargest(3, [4, 5, 8, 2])
Add(3)  → 4
Add(5)  → 5
Add(10) → 5
Add(9)  → 8
Add(4)  → 8

Practice on LeetCode: Kth Largest Element in a Stream

Golang Solution

Keep a min-heap of at most k elements — the heap stores the k largest numbers, so the smallest among them (items[0]) is the kth largest overall. On each push, if size exceeds k, pop the minimum.

Time: O(n log k) to build from nums; each Add is O(log k)
Space: O(k)

import "container/heap"

type KthLargest struct {
	k     int
	items []int
}

func (k KthLargest) Len() int {
	return len(k.items)
}

func (k KthLargest) Less(i, j int) bool {
	return k.items[i] < k.items[j]
}

func (k KthLargest) Swap(i, j int) {
	k.items[i], k.items[j] = k.items[j], k.items[i]
}

func (k *KthLargest) Push(val any) {
	k.items = append(k.items, val.(int))
}

func (k *KthLargest) Pop() any {
	old := k.items
	last := len(old) - 1
	popped := old[last]

	k.items = old[:last]

	return popped
}

func Constructor(k int, nums []int) KthLargest {
	h := &KthLargest{
		k: k,
	}

	for _, num := range nums {
		heap.Push(h, num)

		if h.Len() > k {
			heap.Pop(h)
		}
	}

	return *h
}

func (this *KthLargest) Add(val int) int {
	heap.Push(this, val)

	if this.Len() > this.k {
		heap.Pop(this)
	}

	return this.items[0]
}