Algorithm

Problem Name: 703. Kth Largest Element in a Stream

Design a class to find the `kth` largest element in a stream. Note that it is the `kth` largest element in the sorted order, not the `kth` distinct element.

Implement `KthLargest` class:

• `KthLargest(int k, int[] nums)` Initializes the object with the integer `k` and the stream of integers `nums`.
• `int add(int val)` Appends the integer `val` to the stream and returns the element representing the `kth` largest element in the stream.

Example 1:

```Input
[[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]);
```

Constraints:

• `1 <= k <= 104`
• `0 <= nums.length <= 104`
• `-104 <= nums[i] <= 104`
• `-104 <= val <= 104`
• At most `104` calls will be made to `add`.
• It is guaranteed that there will be at least `k` elements in the array when you search for the `kth` element.

Code Examples

#1 Code Example with Java Programming

```Code - Java Programming```

``````
class KthLargest {

private PriorityQueue pq;
private int k;
public KthLargest(int k, int[] nums) {
this.k = k;
this.pq = new PriorityQueue < >();
for (int num : nums) {
if (pq.size() > k) {
pq.poll();
}
}
}

if (pq.size() > k) {
pq.poll();
}
return pq.peek();
}
}
``````
Copy The Code &

Input

cmd

Output

cmd
[null, 4, 5, 5, 8, 8]

#2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const KthLargest = function(k, nums) {
this.sorted = nums.sort((a, b) => a - b);
this.k = k;
};

let left = 0;
let right = this.sorted.length - 1;
let insertIndex = left;
while (left  < = right) {
let mid = left + Math.floor((right - left) / 2);
if (val > this.sorted[mid]) {
left = mid + 1;
insertIndex = mid + 1;
} else if (val  <  this.sorted[mid]) {
right = mid - 1;
insertIndex = mid;
} else {
insertIndex = mid;
break;
}
}
this.sorted.splice(insertIndex, 0, val);
return this.sorted[this.sorted.length - this.k];
};
``````
Copy The Code &

Input

cmd

Output

cmd
[null, 4, 5, 5, 8, 8]

#3 Code Example with Python Programming

```Code - Python Programming```

``````
class KthLargest(object):

def __init__(self, k, nums):
self.pool = nums
self.k = k
heapq.heapify(self.pool)
while len(self.pool) > k:
heapq.heappop(self.pool)

if len(self.pool) < self.k:
heapq.heappush(self.pool, val)
elif val > self.pool[0]:
heapq.heapreplace(self.pool, val)
return self.pool[0]
``````
Copy The Code &

Input

cmd

Output

cmd
[null, 4, 5, 5, 8, 8]

#4 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
public class _0703_KthLargestElementInAStream
{
private readonly IDictionary < int, int> minHeap;
private int size = 0;

public _0703_KthLargestElementInAStream(int k, int[] nums)
{
this.k = k;
minHeap = new SortedDictionary < int, int>();
foreach (var num in nums)
}

{
if (minHeap.ContainsKey(val))
minHeap[val]++;
else
minHeap[val] = 1;
size++;

if (size > k)
{
var pair = minHeap.First();
if (pair.Value > 1)
minHeap[pair.Key]--;
else
minHeap.Remove(pair.Key);

size--;
}

return minHeap.Keys.First();
}
}

}
``````
Copy The Code &

Input

cmd