How to Solve Kth Largest Element in a Stream

This problem requires implementing a class that dynamically tracks the kth largest element as new values are added. Using a min-heap of size k ensures we can efficiently update and retrieve the current kth largest value in O(log k) time per insertion. GhostInterview guides you through constructing the heap logic and handling edge cases with real-time stream updates.

Problem Statement

You are designing a system for a university admissions office that continuously monitors applicants' test scores. The goal is to always identify the kth highest score among all submitted results to help make dynamic admission decisions as new scores arrive.

Implement the KthLargest class to maintain a stream of integers, supporting real-time additions and returning the kth largest score after each insertion. Your class should be able to initialize with an integer k and an initial array of scores, then efficiently update the kth largest value whenever a new score is added.

Examples

Example 1

Input: ["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]

Output: [null, 4, 5, 5, 8, 8]

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

Example 2

Input: ["KthLargest", "add", "add", "add", "add"] [[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]

Output: [null, 7, 7, 7, 8]

Constraints

• 0 <= nums.length <= 104
• 1 <= k <= nums.length + 1
• -104 <= nums[i] <= 104
• -104 <= val <= 104
• At most 104 calls will be made to add.

Solution Approach

Use a Min-Heap for State Tracking

Maintain a min-heap of size k to store the current k largest elements. The top of the heap always represents the kth largest score. When a new value is added, push it to the heap and remove the smallest element if the heap exceeds size k, keeping the heap size constant.

Initialization with Existing Stream

During initialization, iterate through the given array of numbers and push each into the min-heap while maintaining its size at k. This ensures that before any add operation, the heap correctly represents the current k largest elements in the stream.

Handle Real-Time Additions Efficiently

For each add operation, push the new score into the heap. If the heap size exceeds k, pop the smallest element. Return the top of the heap as the current kth largest value. This guarantees O(log k) time per insertion and correct kth largest tracking at all times.

Complexity Analysis

Time complexity is O((M + N) * log k) where N is initial array length and M is number of add calls; each insertion into a size-k min-heap takes O(log k). Space complexity is O(k) to store the min-heap representing the k largest elements.

What Interviewers Usually Probe

• Ask about handling large dynamic streams and maintaining a fixed-size tracking structure.
• Check if the candidate correctly initializes the heap and updates it with each add operation.
• Probe knowledge of edge cases, such as when the initial array has fewer than k elements.

Common Pitfalls or Variants

Common pitfalls

• Using a full sorted array each time, leading to O(N log N) insertion time per add.
• Forgetting to maintain the heap size at exactly k, causing incorrect kth largest results.
• Not handling duplicate values correctly, which may affect the min-heap top.

Follow-up variants

• Track the kth smallest element in a live data stream instead of the largest.
• Support a stream of real numbers or floats instead of integers with the same heap approach.
• Allow dynamic updates to k during the stream, requiring heap reconstruction or resizing.

How GhostInterview Helps

• GhostInterview provides step-by-step guidance for initializing and updating the min-heap to track the kth largest element.
• It highlights common pitfalls like heap size mismanagement and helps enforce O(log k) efficiency during add operations.
• The solver aids in debugging edge cases with duplicate or negative numbers in a dynamic score stream.

Topic Pages

• Tree
• Design
• Binary Search Tree
• Heap (Priority Queue)
• Binary Tree
• Data Stream

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the most efficient data structure to maintain the kth largest element in a stream?

A min-heap of size k efficiently maintains the kth largest element, ensuring O(log k) insertion and O(1) retrieval.

How does the KthLargest class handle initialization with an existing array?

It iterates through the initial array, inserting each element into the min-heap while maintaining a size of k, ensuring the kth largest element is correct from the start.

What should be returned after each add operation?

After adding a new number, return the top of the min-heap, which represents the current kth largest element in the stream.

Can duplicates affect the kth largest result?

Yes, duplicates should be correctly inserted into the min-heap since the kth largest depends on the exact multiset of values.

How does binary-tree traversal relate to this problem?

The pattern of maintaining a min-heap mirrors binary-tree traversal logic, where we track and update hierarchical state to efficiently find the kth largest element.