551. Kth Loudest Live

EasyHeapDesignData Stream3 hints
RPby Rohit Parihar

A live-stream dashboard wants to show how loud the k-th loudest chat reaction is at any moment. Implement a class KthLoudest whose constructor receives an integer k and an array nums holding the loudness readings recorded so far (the array may be empty).

The method add(value) records one more reading and returns the k-th largest reading seen so far, where equal readings count separately. It is guaranteed that at least k readings exist whenever add is called. The constructor returns nothing. Each call to add should run in O(log k) time and the object should use O(k) memory, so do not re-sort everything on every call.

Example 1

Input:
operations = ["KthLoudest","add","add","add","add","add"]arguments = [[3,[4,5,8,2]],[3],[5],[10],[9],[4]]
Output:
[null,4,5,5,8,8]
Explanation:

Readings sorted are 2,4,5,8; the third largest evolves as 4, 5, 5, 8, 8 while 3, 5, 10, 9 and 4 arrive.

Example 2

Input:
operations = ["KthLoudest","add","add","add"]arguments = [[1,[]],[-3],[-1],[-7]]
Output:
[null,-3,-1,-1]
Explanation:

With k = 1 the answer is simply the maximum so far: -3, then -1, and the smaller -7 changes nothing.

Example 3

Input:
operations = ["KthLoudest","add","add","add"]arguments = [[2,[7,7]],[7],[1],[9]]
Output:
[null,7,7,7]
Explanation:

Duplicates count separately, so the second largest stays 7 after adding 7, 1 and then 9 (readings 9, 7, 7, 7, 1).

Constraints

  • 1 ≤ k ≤ 104
  • 0 ≤ nums.length ≤ 104
  • -109 ≤ nums[i], value ≤ 109
  • At most 104 calls to add
  • At least k readings exist at the moment of every add call (that is, nums.length + 1 ≥ k)

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time
O(log k) per add
Space
O(k)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.