DSAMaster Logo
DSAMaster
BackmediumHeap and Priority Queue

Top K Elements in Stream

Problem Description

You are tasked with designing a data structure, TopKElements, that efficiently tracks the k largest integer elements encountered from a stream of incoming values. Your implementation will be initialized with a specific k and then receive a series of values through an add operation. After all values from an initial array have been processed by the add method, the data structure should be able to report its currently held k largest elements.

Specifically, you need to implement the following:

  1. A class TopKElements.
  2. Its constructor __init__(self, k: int): Initializes the data structure to maintain the k largest elements.
  3. A method add(self, value: int): Processes a new integer value from the stream, updating the collection of top k elements if necessary.

After all add operations for a given set of input values are complete, you should return a list containing the k largest elements present in the collection. If the total number of distinct values added is less than k, return all elements that were added. The order of elements in the returned list does not matter.

Example 1
Input
k = 3 values_to_add = [10, 4, 15, 8, 20]
Output
[20, 15, 10]

Explanation: A `TopKElements` object is initialized with `k=3`. After sequentially adding 10, 4, 15, 8, and 20, the three largest elements maintained are 20, 15, and 10.

Example 2
Input
k = 4 values_to_add = [-5, 2, 1, -3]
Output
[2, 1, -3, -5]

Explanation: With `k=4`, we track the 4 largest elements. Since only 4 elements [-5, 2, 1, -3] are added, all of them are considered the largest.

Constraints

  • 1 <= k <= 10^5
  • 1 <= N <= 10^5 (where N is the total count of values added)
  • -10^9 <= value <= 10^9
00:00
Loading...

Sign in to Solve

Access the full code editor, ThinkBuddy AI hints, and track your progress.

Sign in Free
Test Cases & Output
Enter test input here...
Click "Run Code" to execute