Problem Statement:
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 scoresnums.int add(int val)Adds a new test scorevalto the stream and returns the element representing thekthlargest 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 <= 1041 <= k <= nums.length + 1-104 <= nums[i] <= 104-104 <= val <= 104- At most
104 calls will be made to.add
Approach:
- Insert elements into the heap one by one.
- If the heap size exceeds
k, remove the smallest element (top of the min-heap). - The smallest element in the heap
(heap.front())is always the kth largest in the stream.
Time Complexity:
Time Complexity = O(log k)
Space Complexity:
Space Complexity = O(K)
Dry Run
Input: nums = [3, 2, 1, 5, 6, 4], k = 2
State Transitions:
Initialize: pq = MinPriorityQueue() i = 0 → nums[0] = 3 → pq.enqueue(3) → pq = [3] i = 1 → nums[1] = 2 → pq.enqueue(2) → pq = [2, 3] (min-heap: 2 is root) i = 2 → nums[2] = 1 → pq.enqueue(1) → pq = [1, 3, 2] → pq.size() = 3 > k (2) → pq.dequeue() removes smallest (1) → pq = [2, 3] i = 3 → nums[3] = 5 → pq.enqueue(5) → pq = [2, 3, 5] → pq.size() = 3 > k → pq.dequeue() removes smallest (2) → pq = [3, 5] i = 4 → nums[4] = 6 → pq.enqueue(6) → pq = [3, 5, 6] → pq.size() = 3 > k → pq.dequeue() removes smallest (3) → pq = [5, 6] i = 5 → nums[5] = 4 → pq.enqueue(4) → pq = [4, 6, 5] → pq.size() = 3 > k → pq.dequeue() removes smallest (4) → pq = [5, 6]
Final Output: 5
Explanation: pq.front() returns the smallest in the heap → the 2nd largest element overall.
var KthLargest = function(k, nums) {
this.heap = new MinPriorityQueue();
this.k = k;
for(let i=0; i this.k){
this.heap.dequeue();
}
return this.heap.front();
};
import heapq
class KthLargest:
def __init__(self, k: int, nums: list[int]):
self.min_heap = []
self.k = k
for num in nums:
self.add(num)
def add(self, val: int) -> int:
heapq.heappush(self.min_heap, val)
if len(self.min_heap) > self.k:
heapq.heappop(self.min_heap)
return self.min_heap[0]
import java.util.PriorityQueue;
class KthLargest {
private PriorityQueue minHeap;
private int k;
public KthLargest(int k, int[] nums) {
this.k = k;
minHeap = new PriorityQueue<>();
for (int num : nums) {
add(num);
}
}
public int add(int val) {
minHeap.offer(val);
if (minHeap.size() > k) {
minHeap.poll();
}
return minHeap.peek();
}
}
#include <vector>
#include <queue>
class KthLargest {
private:
std::priority_queue, std::greater> minHeap;
int k;
public:
KthLargest(int k, std::vector& nums) {
this->k = k;
for (int num : nums) {
add(num);
}
}
int add(int val) {
minHeap.push(val);
if (minHeap.size() > k) {
minHeap.pop();
}
return minHeap.top();
}
};
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int *arr;
int size;
int k;
} KthLargest;
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b); // ascending
}
KthLargest* kthLargestCreate(int k, int* nums, int numsSize) {
KthLargest* obj = (KthLargest*)malloc(sizeof(KthLargest));
obj->arr = (int*)malloc(sizeof(int) * (numsSize + 1));
obj->size = 0;
obj->k = k;
for (int i = 0; i < numsSize; i++) {
int val = nums[i];
obj->arr[obj->size++] = val;
qsort(obj->arr, obj->size, sizeof(int), compare);
if (obj->size > k) {
for (int j = 0; j < obj->size - 1; j++)
obj->arr[j] = obj->arr[j + 1];
obj->size--;
}
}
return obj;
}
int kthLargestAdd(KthLargest* obj, int val) {
obj->arr[obj->size++] = val;
qsort(obj->arr, obj->size, sizeof(int), compare);
if (obj->size > obj->k) {
for (int j = 0; j < obj->size - 1; j++)
obj->arr[j] = obj->arr[j + 1];
obj->size--;
}
return obj->arr[0];
}
using System;
using System.Collections.Generic;
public class KthLargest {
private PriorityQueue minHeap;
private int k;
public KthLargest(int k, int[] nums) {
this.k = k;
minHeap = new PriorityQueue();
foreach (int num in nums) {
Add(num);
}
}
public int Add(int val) {
minHeap.Enqueue(val, val);
if (minHeap.Count > k) {
minHeap.Dequeue();
}
return minHeap.Peek();
}
}
