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 integerkand the stream of integersnums.int add(int val)Appends the integervalto the stream and returns the element representing thekthlargest element in the stream.
Example 1:
Input ["KthLargest", "add", "add", "add", "add", "add"] [[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
Constraints:
1 <= k <= 1040 <= nums.length <= 104-104 <= nums[i] <= 104-104 <= val <= 104- At most
104calls will be made toadd. - It is guaranteed that there will be at least
kelements in the array when you search for thekthelement.
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) {
pq.add(num);
if (pq.size() > k) {
pq.poll();
}
}
}
public int add(int val) {
pq.add(val);
if (pq.size() > k) {
pq.poll();
}
return pq.peek();
}
}
Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[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;
};
KthLargest.prototype.add = function(val) {
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];
};
Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[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)
def add(self, val):
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]
Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[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 readonly int k;
private int size = 0;
public _0703_KthLargestElementInAStream(int k, int[] nums)
{
this.k = k;
minHeap = new SortedDictionary < int, int>();
foreach (var num in nums)
Add(num);
}
public int Add(int val)
{
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();
}
}
}
Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]