Implement a class named KthLargest for a growing stream of integers. The class must support two operations:
- KthLargest(k, nums): Initialize rank k and the initial stream nums. - add(value): Append value and return the kth largest stream value after the insertion.
The kth largest value follows sorted order, not distinct-value order. Duplicate values occupy separate positions. Every add call occurs after the stream contains at least k values.
Example 1
Input: [KthLargest(3, [4, 6, 8, 2]), add(5), add(10), add(3)]
Output: [null, 5, 6, 6]
Explanation: The initial stream has 8, 6, and 4 as the three largest values. Insertion of 5 changes the third largest value to 5. Insertion of 10 changes the third largest value to 6. Insertion of 3 leaves the answer at 6.
Example 2
Input: [KthLargest(1, []), add(-3), add(-1), add(-4)]
Output: [null, -3, -1, -1]
Explanation: Rank 1 asks for the largest value. The running answers become -3, -1, and -1, so negative values require no special handling.
Brute Force Approach
The simplest way to find the k-th largest value in a stream is to keep every value seen so far. After each new value arrives, sorting all stored values makes the required rank directly available.
This approach is easy to understand and verify, but it repeatedly sorts the entire stream. As more values arrive, the same elements are sorted again even though only the k-th largest value is needed.
Algorithm
Store
kand all initial stream values so every lateraddoperation can use the complete stream.When a new value arrives, append it to the stored values because it becomes part of the stream.
Copy the stored values before sorting so the original stream remains unchanged for future additions.
Sort the copied array in descending order so the largest values appear first.
Access index
k - 1because zero-based indexing places the k-th largest value at that position.Return the value at index
k - 1as the updated k-th largest element.
Dry Run
kth-largest-stream brute
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: vector<int> numbers; int rank;public: // Initialize the rank and initial stream. Solution(int k, vector<int>& nums) { // Store the requested sorted position. rank = k; // Preserve every initial stream value. numbers = nums; } // Add a value and return the current kth largest. int add(int value) { // Append the newest stream value. numbers.push_back(value); // Copy values so stream history stays unchanged. vector<int> ordered = numbers; // Sort the copy from largest to smallest. sort(ordered.begin(), ordered.end(), greater<int>()); // Rank k uses zero-based index k minus one. return ordered[rank - 1]; }};// Driver codeint main() { vector<int> nums = {4, 6, 8, 2}; Solution obj(3, nums); cout << obj.add(5) << "\n"; cout << obj.add(10) << "\n"; cout << obj.add(3) << "\n"; return 0;}Note: Repeated full sorting may fail for a long stream. Growing collection sizes create excessive work, so an online judge may report Time Limit Exceeded.
Complexity Analysis
Time Complexity: O(S log S) per add operation, where S is the current number of values in the stream, because all S values are copied and sorted. Initial construction takes O(N), where N is the number of initial stream values.
Space Complexity: O(S), because the stored stream and its sorted copy each contain up to S values.
Optimal Approach
The brute force method rebuilds a complete order after every insertion. Only the largest k values can affect the answer. A min-heap of size k keeps exactly the useful group, and the heap root remains the smallest member of the group: the current kth largest value.
Each new value enters the heap. A size above k removes the smallest value. Duplicate values remain separate heap entries, so the kth largest value follows sorted position rather than distinct rank.
Algorithm
Begin with rank
kand an empty min-heap, so storage can stay limited to the largestkvalues.Feed every initial value into the heap, allowing each number to compete for a place in the top-k group.
Remove the heap root after size exceeds
kbecause the smallest candidate cannot remain among the largestkvalues.Reuse the same push-and-trim rule for every
addcall, preserving the top-k group after each insertion.Keep at most
kvalues in the heap so stream growth never increases the maintained working set.Return the heap root because the smallest value among the largest
kvalues has overall rankk.
Dry Run
kth-largest-stream optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: priority_queue<int, vector<int>, greater<int>> minHeap; int rank;public: // Initialize the tracker with the top k values. Solution(int k, vector<int>& nums) { // Store the requested sorted position. rank = k; // Process every initial stream value. for (int value : nums) { // Add a new candidate for the top k group. minHeap.push(value); // Extra size means the smallest value is unneeded. if (minHeap.size() > rank) { minHeap.pop(); } } } // Add a value and return the current kth largest. int add(int value) { // Add a new candidate for the top k group. minHeap.push(value); // Extra size means the smallest value is unneeded. if (minHeap.size() > rank) { minHeap.pop(); } // The smallest top-k value has overall rank k. return minHeap.top(); }};// Driver codeint main() { vector<int> nums = {4, 6, 8, 2}; Solution obj(3, nums); cout << obj.add(5) << "\n"; cout << obj.add(10) << "\n"; cout << obj.add(3) << "\n"; return 0;}Complexity Analysis
Time Complexity: O(log k) per add operation, because each call performs one heap insertion and at most one removal on a heap of size at most k. Building the initial heap from N values takes O(N log k), where N is the number of initial stream values.
Space Complexity: O(k), because the min-heap stores at most k values regardless of the total stream length.
Interview follow-up Questions
A size-k min-heap stores the largest k stream values. The smallest stored value has rank k among all processed values and stays at the heap root.
Be the first to add a comment.