Kth Largest Element in a Stream

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

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

Create a free account to view this lesson.

By signing up, you agree to Educative's Terms of Service and Privacy Policy