Kth Largest Element in a Stream

Explore how to implement a class that tracks the kth largest element in a stream of scores dynamically. Understand real-time updates and efficient use of heaps to manage data while maintaining performance and correctness. Practice coding this solution in C++ to prepare for interview questions on streaming and priority data.

We'll cover the following...

Statement
Examples
Understand the problem
Figure it out!
Try it yourself

Statement

You are part of a university admissions office that needs to dynamically track the k^th highest test score among applicants in real time. This functionality is critical for determining cutoff marks for interviews and admissions as new applicants continue to submit their scores.

You need to implement a class that, given an integer, k, manages a continuous stream of test scores. Each time a new score is added, the class should return the k^th highest score among all scores received so far, i.e., the score that would appear in the $k^{th}$ position if the scores were sorted in descending order.

Implement the KthLargest class:

Constructor: Initializes the object with the integer k and the initial stream of test scores nums.
int add(int val): This function adds a new test score val to the stream and returns the k^th highest score among all scores seen so far.