Solution: Kth Largest Element in a Stream

Understand how to implement and optimize a solution to find the kth largest element in a dynamic stream of numbers. Explore building a min heap structure to maintain the top k elements and efficiently update it for each new input, enabling quick retrieval of the kth largest score at any time.

We'll cover the following...

Statement
Solution
- Naive approach
- Optimized approach using Top K Elements

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.