Kth Largest in a Stream

Problem Understanding

We are given:

• An integer array arr[] representing a stream of incoming numbers.

• An integer k.

After each insertion into the stream, we must find the Kth largest element among all elements seen so far.

If fewer than k elements exist, return -1.

Example

Input:

arr = [1, 2, 3, 4, 5, 6]
k = 4

Output:

[-1, -1, -1, 1, 2, 3]

Why?

Stream So Far	Sorted Order	4th Largest
[1]	[1]	-1
[1,2]	[2,1]	-1
[1,2,3]	[3,2,1]	-1
[1,2,3,4]	[4,3,2,1]	1
[1,2,3,4,5]	[5,4,3,2,1]	2
[1,2,3,4,5,6]	[6,5,4,3,2,1]	3

Efficient Approach Using Min Heap

Key Observation

We do NOT need all elements sorted every time.

We only need the top k largest elements.

A Min Heap of size k is perfect for this.

Why Min Heap?

Suppose k = 4.

We keep only the 4 largest numbers in the heap.

Example:

Heap = [3,4,5,6]

The smallest among them is 3.

That means:

3 = 4th largest element

Because there are exactly 3 numbers larger than it.

Algorithm

For every number in the stream:

1. Insert number into Min Heap.

2. If heap size exceeds k, remove smallest element.

3. If heap size is still less than k, answer is -1.

4. Otherwise, heap top (peek) is the Kth largest element.

Dry Run

Input:

arr = [1,2,3,4,5,6]
k = 4

Step-by-Step

Current Number	Heap After Processing	Answer
1	[1]	-1
2	[1,2]	-1
3	[1,2,3]	-1
4	[1,2,3,4]	1
5	[2,3,4,5]	2
6	[3,4,5,6]	3

Final Output:

[-1, -1, -1, 1, 2, 3]

Java Solution

import java.util.*;

class Solution {
    
    static ArrayList<Integer> kthLargest(int[] arr, int k) {

        ArrayList<Integer> result = new ArrayList<>();

        // Min Heap
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int num : arr) {

            // Insert current number
            pq.add(num);

            // Keep only k largest elements
            if (pq.size() > k) {
                pq.poll();
            }

            // If less than k elements exist
            if (pq.size() < k) {
                result.add(-1);
            } else {

                // Top of heap = kth largest
                result.add(pq.peek());
            }
        }

        return result;
    }
}

Complexity Analysis

Time Complexity

Each insertion/removal in heap takes:

O(log k)

For n elements:

O(n log k)

Space Complexity

Heap stores at most k elements:

O(k)

Important Interview Points

Why Use Min Heap Instead of Max Heap?

A Max Heap would store all elements, and retrieving the kth largest becomes inefficient.

A Min Heap of size k keeps only useful elements.

Core Logic

The heap always contains:

k largest elements seen so far

And:

smallest among them = kth largest overall

Edge Cases

Case 1

arr = [5]
k = 2

Output:

[-1]

Because 2 elements do not exist.

Case 2

arr = [3,3,3]
k = 2

Output:

[-1,3,3]

Duplicates are allowed because the problem says:

NOT kth unique largest

Conclusion

This problem is a classic application of:

• Heap / Priority Queue

• Streaming Data Processing

• Top K Elements Pattern

The optimal strategy is:

• Maintain a Min Heap of size k

• Heap top always gives the Kth largest element

• Efficient complexity: O(n log k)

Summary

This problem demonstrates how a Min Heap can efficiently track the Kth largest element in a stream of numbers. By maintaining only the top k largest elements in the heap, we avoid unnecessary sorting and achieve an optimized time complexity of O(n log k) with O(k) extra space. The approach is widely used in streaming systems, real-time analytics, and Top K problems.