Search⌘ K
AI Features
Home
Courses
Coderust: Hacking the Coding Interview

Kth Largest Element in a Stream

Explore how to design a class that maintains the kth largest element from an ongoing stream of integers. Understand the use of min-heaps to efficiently add new values and extract the kth largest element quickly. This lesson helps build skills in algorithm design, data structure selection, and complexity analysis for dynamic data streams.

We'll cover the following...

Statement

Given an infinite stream of integers, design a class to find the kthk^{th} largest element in a stream.

Note: It is the kthk^{th} largest element in the sorted order, not the kthk^{th} distinct element.

Implementation of the class should be:

  • Initializes the object with the integer kk and the stream of integers.
  • The add(value) function appends the value to the stream and returns the element that represents the kthk^{th}
...