LeetCode Entry

703. Kth Largest Element in a Stream

12.08.2024 easy 2024 kotlin rust

kth largest in a stream of values

703. Kth Largest Element in a Stream easy blog post substack youtube 1.webp

Problem TLDR

kth largest in a stream of values #easy #heap

Intuition

Use the heap.

Approach

In Kotlin PriorityQueue is a max-heap, in Rust BinaryHeap is a min-heap.

Complexity

  • Time complexity: \(O(log(k))\) for add operation, O(nlog(k)) total

  • Space complexity: \(O(k)\)

Code


class KthLargest(val k: Int, nums: IntArray) {
    val pq = PriorityQueue<Int>()
    init { for (n in nums) add(n) }
    fun add(v: Int) = pq
        .run { pq += v; if (size > k) poll(); peek() }
}



struct KthLargest { bh: BinaryHeap<i32>, k: usize }
impl KthLargest {
    fn new(k: i32, nums: Vec<i32>) -> Self {
        let mut kth =  Self { bh: BinaryHeap::new(), k: k as usize };
        for &n in nums.iter() { kth.add(n); }
        kth
    }
    fn add(&mut self, val: i32) -> i32 {
        self.bh.push(-val);
        if self.bh.len() > self.k { self.bh.pop(); }
        -self.bh.peek().unwrap()
    }
}