703. Kth Largest Element in a Stream

Problem Description

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

Examples:

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 ≤ 10⁴
• 0 ≤ nums.length ≤ 10⁴
• -10⁴ ≤ nums[i] ≤ 10⁴
• -10⁴ ≤ val ≤ 10⁴
• At most 10⁴ 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 k^th element

Python Solution

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.heap = []
        for num in nums:
            self.add(num)

    def add(self, val: int) -> int:
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        return self.heap[0]

Implementation Notes:

• Uses min heap to maintain k largest elements
• Time complexity: O(log k) for add operation
• Space complexity: O(k) to store the heap

Java Solution

class KthLargest {
    private final int k;
    private final PriorityQueue heap;
    
    public KthLargest(int k, int[] nums) {
        this.k = k;
        heap = new PriorityQueue<>();
        for (int num : nums) {
            add(num);
        }
    }
    
    public int add(int val) {
        heap.offer(val);
        if (heap.size() > k) {
            heap.poll();
        }
        return heap.peek();
    }
}

C++ Solution

class KthLargest {
private:
    int k;
    priority_queue, greater> heap;
    
public:
    KthLargest(int k, vector& nums) {
        this->k = k;
        for (int num : nums) {
            add(num);
        }
    }
    
    int add(int val) {
        heap.push(val);
        if (heap.size() > k) {
            heap.pop();
        }
        return heap.top();
    }
};

JavaScript Solution

/**
 * @param {number} k
 * @param {number[]} nums
 */
var KthLargest = function(k, nums) {
    this.k = k;
    this.heap = new MinPriorityQueue();
    nums.forEach(num => this.add(num));
};

/** 
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function(val) {
    this.heap.enqueue(val);
    if (this.heap.size() > this.k) {
        this.heap.dequeue();
    }
    return this.heap.front().element;
};

C# Solution

public class KthLargest {
    private readonly int k;
    private readonly PriorityQueue heap;
    
    public KthLargest(int k, int[] nums) {
        this.k = k;
        heap = new PriorityQueue();
        foreach (int num in nums) {
            Add(num);
        }
    }
    
    public int Add(int val) {
        heap.Enqueue(val, val);
        if (heap.Count > k) {
            heap.Dequeue();
        }
        return heap.Peek();
    }
}

Implementation Notes:

• Uses min heap (priority queue) to maintain k largest elements
• Heap size is kept at k elements
• Time complexity: O(log k) for add operation
• Space complexity: O(k) to store the heap