LeetCode Entry

703. Kth Largest Element in a Stream

23.05.2023 medium 2023 kotlin

Kth largest

703. Kth Largest Element in a Stream medium blog post substack

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/221

Problem TLDR

Kth largest

Intuition

We need to keep all values smaller than current largest kth element and can safely drop all other elements.

Approach

Use PriorityQueue.

Complexity

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

Code

class KthLargest(val k: Int, nums: IntArray) {
    val pq = PriorityQueue<Int>(nums.toList())

        fun add(v: Int): Int = with (pq) {
            add(v)
            while (size > k) poll()
            peek()
        }
    }