LeetCode 0703. Kth Largest Element in a Stream Solution in Java, Python, C++, JavaScript, Go & Rust | Explanation + Code

Description

You are part of a university admissions office and need to keep track of the kth highest test score from applicants in real-time. This helps to determine cut-off marks for interviews and admissions dynamically as new applicants submit their scores.

You are tasked to implement a class which, for a given integer k, maintains a stream of test scores and continuously returns the kth highest test score after a new score has been submitted. More specifically, we are looking for the kth highest score in the sorted list of all scores.

Implement the KthLargest class:

• KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of test scores nums.
• int add(int val) Adds a new test score val to the stream and returns the element representing the kth largest element in the pool of test scores so far.

 

Example 1:

Input:
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]

Output: [null, 4, 5, 5, 8, 8]

Explanation:

KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8

Example 2:

Input:
["KthLargest", "add", "add", "add", "add"]
[[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]

Output: [null, 7, 7, 7, 8]

Explanation:

KthLargest kthLargest = new KthLargest(4, [7, 7, 7, 7, 8, 3]);
kthLargest.add(2); // return 7
kthLargest.add(10); // return 7
kthLargest.add(9); // return 7
kthLargest.add(9); // return 8

 

Constraints:

• 0 <= nums.length <= 104
• 1 <= k <= nums.length + 1
• -104 <= nums[i] <= 104
• -104 <= val <= 104
• At most 104 calls will be made to add.

Solutions

Solution 1: Priority Queue (Min Heap)

We maintain a priority queue (min heap) minQ.

Initially, we add the elements of the array nums to minQ one by one, ensuring that the size of minQ does not exceed k. The time complexity is O(n × log k).

Each time a new element is added, if the size of minQ exceeds k, we pop the top element of the heap to ensure that the size of minQ is k. The time complexity is O(log k).

In this way, the elements in minQ are the largest k elements in the array nums, and the top element of the heap is the k^{th} largest element.

The space complexity is O(k).

PythonJavaC++GoTypeScriptJavaScript

class KthLargest: def __init__(self, k: int, nums: List[int]): self.k = k self.min_q = [] for x in nums: self.add(x) def add(self, val: int) -> int: heappush(self.min_q, val) if len(self.min_q) > self.k: heappop(self.min_q) return self.min_q[0] # Your KthLargest object will be instantiated and called as such: # obj = KthLargest(k, nums) # param_1 = obj.add(val)(code-box)

class KthLargest { private PriorityQueue<Integer> minQ; private int k; public KthLargest(int k, int[] nums) { this.k = k; minQ = new PriorityQueue<>(k); for (int x : nums) { add(x); } } public int add(int val) { minQ.offer(val); if (minQ.size() > k) { minQ.poll(); } return minQ.peek(); } } /** * Your KthLargest object will be instantiated and called as such: * KthLargest obj = new KthLargest(k, nums); * int param_1 = obj.add(val); */(code-box)

class KthLargest { public: KthLargest(int k, vector<int>& nums) { this->k = k; for (int x : nums) { add(x); } } int add(int val) { minQ.push(val); if (minQ.size() > k) { minQ.pop(); } return minQ.top(); } private: int k; priority_queue<int, vector<int>, greater<int>> minQ; }; /** * Your KthLargest object will be instantiated and called as such: * KthLargest* obj = new KthLargest(k, nums); * int param_1 = obj->add(val); */(code-box)

type KthLargest struct { k int minQ hp } func Constructor(k int, nums []int) KthLargest { minQ := hp{} this := KthLargest{k, minQ} for _, x := range nums { this.Add(x) } return this } func (this *KthLargest) Add(val int) int { heap.Push(&this.minQ, val) if this.minQ.Len() > this.k { heap.Pop(&this.minQ) } return this.minQ.IntSlice[0] } type hp struct{ sort.IntSlice } func (h *hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] } func (h *hp) Pop() interface{} { old := h.IntSlice n := len(old) x := old[n-1] h.IntSlice = old[0 : n-1] return x } func (h *hp) Push(x interface{}) { h.IntSlice = append(h.IntSlice, x.(int)) } /** * Your KthLargest object will be instantiated and called as such: * obj := Constructor(k, nums); * param_1 := obj.Add(val); */(code-box)

class KthLargest { #k: number = 0; #minQ = new MinPriorityQueue<number>(); constructor(k: number, nums: number[]) { this.#k = k; for (const x of nums) { this.add(x); } } add(val: number): number { this.#minQ.enqueue(val); if (this.#minQ.size() > this.#k) { this.#minQ.dequeue(); } return this.#minQ.front(); } } /** * Your KthLargest object will be instantiated and called as such: * var obj = new KthLargest(k, nums) * var param_1 = obj.add(val) */(code-box)

/** * @param {number} k * @param {number[]} nums */ var KthLargest = function (k, nums) { this.k = k; this.minQ = new MinPriorityQueue(); for (const x of nums) { this.add(x); } }; /** * @param {number} val * @return {number} */ KthLargest.prototype.add = function (val) { this.minQ.enqueue(val); if (this.minQ.size() > this.k) { this.minQ.dequeue(); } return this.minQ.front(); }; /** * Your KthLargest object will be instantiated and called as such: * var obj = new KthLargest(k, nums) * var param_1 = obj.add(val) */(code-box)