Kth Largest Element in a Stream

Kth Largest Element in a Stream is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Heap (Priority Queue) Patterns pattern, in the Top K Elements (Selection/Frequency) subpattern.

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 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]);

Topics and companies

Topics: Tree, Design, Binary Search Tree, Heap (Priority Queue), Binary Tree, Data Stream.

Reported in interviews at Amazon, Microsoft, Box, Facebook.

How to practise Kth Largest Element in a Stream on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(log k) per add() call. Initial construction is O(n log k), where n is the size of nums. Each add() operation pushes and possibly pops from a min-heap of size at most k. time and O(k), since the min-heap never stores more than k elements at any time. space.

Open Kth Largest Element in a Stream in the code editor, or read the Kth Largest Element in a Stream editorial for a worked solution with its approach and complexity analysis.

Where Kth Largest Element in a Stream sits in the DSA pattern sheet

Problems related to Kth Largest Element in a Stream

Other problems that use the same Top K Elements (Selection/Frequency) and Heap (Priority Queue) Patterns techniques:

Preparing this workspace.