703.kth-largest-element-in-a-stream.md

703. Kth Largest Element in a Stream

Heap

To find the kth largest element in a stream, we can use a min heap of fixed size k to maintain the k largest elements.

class KthLargest(private val k: Int, private val nums: IntArray) {

    private val minHeap = PriorityQueue<Int>()

    init {
        for (num in nums) {
            add(num)
        }
    }

    fun add(`val`: Int): Int {
        minHeap.add(`val`)
        if (minHeap.size > k) minHeap.poll()

        // Fixed size `k` min heap, the peek is the kth largest element
        return minHeap.peek()
    }
}