Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Kth Largest Element in a Stream

Understand how to design a class that maintains the kth largest element from a continuous stream of values. Explore heap data structures and implement methods for optimizing real-time updates as new scores arrive.

We'll cover the following...

Statement

You are part of a university admissions office that needs to dynamically track the kth 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 kth highest score among all scores received so far, i.e., the score that would appear in the kthk^{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 kth highest score among all scores seen so far.

Constraints:

  • 1≤k≤1031 \leq k \leq 10^3
  • 0≤0 \leq nums.length ≤103\leq 10^3
  • −103≤-10^3 \leq nums[i] ≤103\leq 10^3
  • −103≤-10^3 \leq value ≤103\leq 10^3
  • At most, 10310^3 calls will be made to add.
  • It is guaranteed that there will be at least kk elements in the array when you search for the kthk^{th} element.

Examples

canvasAnimation-image
1 / 5

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Kth Largest Element in a Stream

1.

KthLargest (2, [10, 7, 11, 5])

What does the call add(12) return?

A.

55

B.

1010

C.

1111

D.

1212

1 / 3

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Sequence - Vertical
Drag and drop the cards to re-arrange them in the correct sequence
1
2
3
4
5

Try it yourself

Implement your solution in the following coding playground.

Java
usercode > KthLargest.java
import java.util.*;
class KthLargest {
	// constructor to initialize topKHeap and add values in it
	public KthLargest(int k, int[] nums) {
		// Write your code Here
	}
	// adds element in the topKHeap
	public int add(int val) {
		// Replace this placeholder return statement with your code
		return -1;
	}	
}
Kth Largest Element in a Stream