grid47 Exploring patterns and algorithms
Aug 28, 2024
6 min read
Solution to LeetCode 703: Kth Largest Element in a Stream Problem
You are tasked with implementing a class that helps track the kth highest score in a dynamic list of test scores. Each time a new score is submitted, you need to return the kth highest score in the list.
Problem
Approach
Steps
Complexity
Input: The class should be initialized with an integer k (the desired ranking) and a list of test scores. For each new score added to the stream, return the kth highest score in the list.
• At most 10^4 calls will be made to the add method.
Output: The method should return the kth largest number in the list after each new score is added.
Example: Output: [null, 5, 6, 7, 7]
Constraints:
• The result after each call to add should be the kth largest score in the current list of test scores.
Goal: Track the kth largest score dynamically using a priority queue or a min-heap to efficiently maintain the list of the top k scores.
Steps:
• 1. Initialize a priority queue (min-heap) to store the top k elements.
• 2. Add each score to the heap.
• 3. If the heap exceeds k elements, remove the smallest element.
• 4. After each addition, the top of the heap will be the kth largest score.
Goal: The problem must handle dynamic updates to the list of scores.
Steps:
• The class must handle multiple calls to the add method efficiently.
• The list of scores can vary in size from 0 to 10,000.
Assumptions:
• The list will be dynamically updated with new scores.
• The kth largest element should be returned after each new score is added.
• Input: Input: KthLargest(2, [1, 3, 5, 7, 9])
• Explanation: When the 2nd largest element is requested after each new score is added, the following occurs: add(6) => 6 becomes the 2nd largest number, add(8) => 7 becomes the 2nd largest number, etc.
Approach: The goal is to efficiently manage a dynamic list of scores and find the kth largest element after each insertion. A priority queue or min-heap can be used to keep track of the top k elements in the stream.
Observations:
• A heap is a good choice to manage a dynamic list of top k elements efficiently.
• Since we are only interested in the kth largest element, using a min-heap of size k ensures that the smallest element in the heap is always the kth largest.
Steps:
• Step 1: Initialize the KthLargest class with an integer k and a list of scores.
• Step 2: Use a priority queue (min-heap) to store the top k elements.
• Step 3: Add a new score to the heap and ensure the heap contains at most k elements.
• Step 4: After each insertion, return the smallest element in the heap, which represents the kth largest score.
Empty Inputs:
• The list of scores may be empty initially, but k will always be valid.
Large Inputs:
• If the number of scores is very large, ensure that the heap operations are optimized to handle up to 10,000 elements.
Special Values:
• If multiple scores have the same value, they should be treated as equal for the purposes of finding the kth largest score.
Constraints:
• Ensure the heap is only storing the top k elements at all times to maintain efficiency.
priority_queue<int, vector<int>, greater<int>> pq;
int k;
KthLargest(int k, vector<int>& nums) {
this->k = k;
for(autox: nums) {
pq.push(x);
if(pq.size() > k) {
cout << pq.top();
pq.pop();
}
}
}
intadd(int val) {
pq.push(val);
if(pq.size() > k) {
pq.pop();
}
return pq.top();
}
};
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest* obj = new KthLargest(k, nums);
* int param_1 = obj->add(val);
