Kth Largest Integer in a Stream

Estimated reading: 3 minutes 94 views

Design a class to find the kth largest integer in a stream of values, which may include duplicates. The stream is not necessarily sorted.

Class Definition:

KthLargest(int k, int[] nums): Initializes the object with an integer k and a stream of integers nums.
int add(int val): Adds the integer val to the stream and returns the kth largest integer from the stream after this addition.

Example:

Input:

css

["KthLargest", [3, [1, 2, 3, 3]], "add", [3], "add", [5], "add", [6], "add", [7], "add", [8]]

Output:

csharp

[null, 3, 3, 3, 5, 6]

Explanation:

scss

KthLargest kthLargest = new KthLargest(3, [1, 2, 3, 3]);
kthLargest.add(3);   // returns 3
kthLargest.add(5);   // returns 3
kthLargest.add(6);   // returns 3
kthLargest.add(7);   // returns 5
kthLargest.add(8);   // returns 6

Constraints:

1 <= k <= 1000
0 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-1000 <= val <= 1000
There will always be at least k integers in the stream when searching for the kth largest integer.

				
					    private PriorityQueue<Integer> minHeap;
     private int k;

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

    public int add(int val) {
        minHeap.offer(val);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
        return minHeap.peek();
    }

Constructor

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

The constructor initializes the heap (minHeap) and stores the k value.
Then, for each number in the input array nums, the number is added to the heap using minHeap.offer(num).
After each addition, we check if the size of the heap exceeds k. If it does, we remove the smallest element using minHeap.poll(). This that the heap always contains only the k largest elements.
The smallest element in the heap (which is at the root) is the kth largest overall element.

Add Method

				
					public int add(int val) {
    minHeap.offer(val);
    if (minHeap.size() > k) {
        minHeap.poll();
    }
    return minHeap.peek();
}

The add(int val) method adds a new value val to the heap.
After adding the value, if the heap’s size exceeds k, the smallest element is removed to maintain only k elements in the heap.
The top of the heap (minHeap.peek()) now contains the kth largest element because the heap contains the k largest elements, with the smallest of them at the top.

How the Min-Heap is Used:

The key idea here is that we want to maintain the k largest elements, so by using a min-heap:

Keep only the largest k elements in the heap.
The smallest of these k largest elements (which is the kth largest overall) is always at the top of the heap.
Whenever a new number is added, if it makes the size of the heap exceed k, the smallest element is discarded, ensuring the heap keeps only the k largest numbers.