Kth Largest in a Stream

Intuition

After processing each element we need the k-th largest seen so far. A min-heap of exactly k elements does this in O(log k) per step: the heap always holds the k largest elements, and its minimum (the top) is exactly the k-th largest. Before k elements have been seen, no k-th largest exists, so output -1.

Algorithm

1Create a min-heap (PriorityQueue with natural order).
2For each element in arr: add it to the heap.
3If heap size exceeds k, evict the minimum (poll).
4If heap size equals k, append heap.peek() to result; otherwise append -1.
5Return the result list.

Example Walkthrough

Input: arr = [1, 2, 3, 4, 5], k = 2

1.i=0: heap=[1], size<2 → output -1.
2.i=1: heap=[1,2], size=2 → output peek=1.
3.i=2: add 3 → heap=[1,2,3], evict min → heap=[2,3] → output 2.
4.i=3: add 4 → heap=[2,3,4], evict min → heap=[3,4] → output 3.
5.i=4: add 5 → heap=[3,4,5], evict min → heap=[4,5] → output 4.

Output: [-1, 1, 2, 3, 4]

Common Pitfalls

•Java's PriorityQueue is a min-heap by default — no comparator needed here.
•Check heap size == k (not >= k) before peeking, since after eviction size is always ≤ k.
•Output -1 for early indices — do not peek when the heap has fewer than k elements.

Kth Largest in a Stream.java

Java


// Approach: Maintain a min-heap of size k. For each element, add it and evict the min if size exceeds k.
// The heap's top (minimum) is the k-th largest seen so far. Output -1 until k elements have been processed.
// Time: O(n log k) Space: O(k)
import java.util.*;

class Solution {

    static ArrayList<Integer> kthLargest(int[] arr, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            pq.add(arr[i]);
            if (pq.size() > k) {
                pq.poll();
            }

            res.add(pq.size() == k ? pq.peek() : -1);
        }
        return res;
    }
}

Was this solution helpful?