kth-largest-element-in-a-stream

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

Algorithms

You are part of a university admissions office and need to keep track of the <code>kth</code> highest test score from applicants in real-time. This helps to determine cut-off marks for interviews and admissions dynamically as new applicants submit their scores.

You are tasked to implement a class which, for a given integer&nbsp;<code>k</code>, maintains a stream of test scores and continuously returns the&nbsp;<code>k</code>th highest test score&nbsp;after&nbsp;a new score has been submitted. More specifically, we are looking for the <code>k</code>th highest score in the sorted list of all scores.

Implement the&nbsp;<code>KthLargest</code> class:

<ul>
	<li><code>KthLargest(int k, int[] nums)</code> Initializes the object with the integer <code>k</code> and the stream of test scores&nbsp;<code>nums</code>.</li>
	<li><code>int add(int val)</code> Adds a new test score&nbsp;<code>val</code> to the stream and returns the element representing the <code>kth</code> largest element in the pool of test scores so far.</li>
</ul>

&nbsp;
Example 1:

<div class="example-block">
Input: 
[&quot;KthLargest&quot;, &quot;add&quot;, &quot;add&quot;, &quot;add&quot;, &quot;add&quot;, &quot;add&quot;] 
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]

Output: [null, 4, 5, 5, 8, 8]

Explanation:

KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); 
kthLargest.add(3); // return 4 
kthLargest.add(5); // return 5 
kthLargest.add(10); // return 5 
kthLargest.add(9); // return 8 
kthLargest.add(4); // return 8
</div>

Example 2:

<div class="example-block">
Input: 
[&quot;KthLargest&quot;, &quot;add&quot;, &quot;add&quot;, &quot;add&quot;, &quot;add&quot;] 
[[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]

Output: [null, 7, 7, 7, 8]

Explanation:
KthLargest kthLargest = new KthLargest(4, [7, 7, 7, 7, 8, 3]); 
kthLargest.add(2); // return 7 
kthLargest.add(10); // return 7 
kthLargest.add(9); // return 7 
kthLargest.add(9); // return 8</div>

&nbsp;
Constraints:

<ul>
	<li><code>0 &lt;= nums.length &lt;= 104</code></li>
	<li><code>1 &lt;= k &lt;= nums.length + 1</code></li>
	<li><code>-104 &lt;= nums[i] &lt;= 104</code></li>
	<li><code>-104 &lt;= val &lt;= 104</code></li>
	<li>At most <code>104</code> calls will be made to <code>add</code>.</li>
</ul>