Kth Largest Element in a Stream

Try to solve the Kth Largest Element in a Stream problem.

We'll cover the following

Statement#

Given an infinite stream of integers (sorted or unsorted), nums, 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.

The class should have the following functions, inputs, and return values:

  • Init(nums, k): It takes an array of integers nums and an integer k and initializes the class object.

  • Add(value): It takes one integer value, appends it to the stream, and returns the element representing the kthk^{th} largest element in the stream.

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 of 5

canvasAnimation-image

2 of 5

canvasAnimation-image

3 of 5

canvasAnimation-image

4 of 5

canvasAnimation-image

5 of 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:

KthK^{th} Largest Element in an Array

1

Given the following inputs, what will be the output?

nums = [4, 2, 1, 3, 5, 8]

k = 5

A)

9

B)

2

C)

8

D)

5

Question 1 of 40 attempted

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.

Drag and drop the cards to re-arrange them in the correct sequence

Initialize a min heap in the constructor. Iterate through the elements in nums and call the add function for each element.

In the add function, check if the length of the heap is less than k.

If TRUE, push the number onto the heap. Otherwise, compare the number with the smallest element (root of the heap).

If the number is greater than the smallest element, pop the smallest element and then push the number onto the heap.

After adding all the numbers, the kth largest element can be found at the root of the heap.

Try it yourself#

Implement your solution in the following coding playground:

Python
usercode > Kth_largest.py
Input #1
Input #2
Kth Largest Element in a Stream

Top K Elements: Introduction

Solution: Kth Largest Element in a Stream