Kth Largest Element In A Stream - Leetcode Solution

Problem Statement:

The kth largest element in a stream is the kth largest element that appears in an infinite stream (i.e., a stream of integers that are not finite and are not predetermined). Implement the KthLargest class:

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

Solution:

We can use a max heap to store the k largest elements seen so far in the stream. We initialize our heap with the first k elements of the stream, and then for every new element, we compare it with the root of our heap (which is the largest element seen so far), if the new element is smaller than the root of the heap, we can discard it since it cannot be one of the k largest elements in the stream. However, if the new element is larger than the root of the heap (i.e., it potentially could be one of the k largest elements in the stream), we add it to the heap and remove the smallest element in the heap since it has been replaced by a larger element. The kth largest element in the stream is always the root of the heap.

Algorithm:

1. Initialize an empty max heap of size k.
2. Add the first k elements of the stream to the max heap.
3. For every new element x in the stream: a. If x is smaller than or equal to the root of the heap, ignore it. b. If x is larger than the root of the heap, add it to the heap and remove the smallest element in the heap.
4. The kth largest element in the stream is the root of the heap.

Time Complexity:

Adding an element to a heap takes O(log k) time, and we perform this operation for every element in the stream, so the total time complexity is O(n log k), where n is the length of the stream.

Space Complexity:

We are using a max heap of size k to store the k largest elements seen so far in the stream, so the space complexity is O(k).

Code:

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

1