Problem Statement
Stream Data Processor
You're building a data processing system that needs to track the kth largest element in a continuous stream of numbers.
Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Your class will have a constructor which accepts an integer k and an integer array nums, which contains initial elements from the stream. For each call to the method add, return the element representing the kth largest element in the stream.
Examples
Example 1:
Input: KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // returns 4
kthLargest.add(5); // returns 5
kthLargest.add(10); // returns 5
kthLargest.add(9); // returns 8
kthLargest.add(4); // returns 8
Output: [null, 4, 5, 5, 8, 8]
Explanation: KthLargest(3, [4, 5, 8, 2]): The 3rd largest element is 4.
add(3): The elements are [2, 3, 4, 5, 8], the 3rd largest is 4.
add(5): The elements are [2, 3, 4, 5, 5, 8], the 3rd largest is 5.
add(10): The elements are [2, 3, 4, 5, 5, 8, 10], the 3rd largest is 5.
add(9): The elements are [2, 3, 4, 5, 5, 8, 9, 10], the 3rd largest is 8.
add(4): The elements are [2, 3, 4, 4, 5, 5, 8, 9, 10], the 3rd largest is 8.
Constraints
- 1 <= k <= 10^4
- 0 <= nums.length <= 10^4
- -10^4 <= nums[i] <= 10^4
- -10^4 <= val <= 10^4
- At most 10^4 calls will be made to add
- It is guaranteed that there will be at least k elements in the array when you search for the kth element
Problem Breakdown
To solve this problem, we need to:
- We need to efficiently track the kth largest element in a stream of numbers
- A min heap of size k can be used to maintain the k largest elements
- When a new element is added, we add it to the heap and remove the smallest element if the heap size exceeds k
- The top of the heap will always be the kth largest element
- This approach is more efficient than sorting the entire array each time a new element is added
- The problem is a classic application of the heap data structure
String Problems
Learning Objective
Apply string manipulation concepts to solve a real-world problem.
Stream Data Processor
You're building a data processing system that needs to track the kth largest element in a continuous stream of numbers.
Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Your class will have a constructor which accepts an integer k and an integer array nums, which contains initial elements from the stream. For each call to the method add, return the element representing the kth largest element in the stream.
Examples
Example 1:
KthLargest(3, [4, 5, 8, 2]): The 3rd largest element is 4. add(3): The elements are [2, 3, 4, 5, 8], the 3rd largest is 4. add(5): The elements are [2, 3, 4, 5, 5, 8], the 3rd largest is 5. add(10): The elements are [2, 3, 4, 5, 5, 8, 10], the 3rd largest is 5. add(9): The elements are [2, 3, 4, 5, 5, 8, 9, 10], the 3rd largest is 8. add(4): The elements are [2, 3, 4, 4, 5, 5, 8, 9, 10], the 3rd largest is 8.
Problem Breakdown
Constraints:
- 1 <= k <= 10^4
- 0 <= nums.length <= 10^4
- -10^4 <= nums[i] <= 10^4
- -10^4 <= val <= 10^4
- At most 10^4 calls will be made to add
- It is guaranteed that there will be at least k elements in the array when you search for the kth element
Key Insights:
We need to efficiently track the kth largest element in a stream of numbers
A min heap of size k can be used to maintain the k largest elements
When a new element is added, we add it to the heap and remove the smallest element if the heap size exceeds k
The top of the heap will always be the kth largest element
This approach is more efficient than sorting the entire array each time a new element is added
The problem is a classic application of the heap data structure
Real-World Application
This problem has several practical applications:
Data Stream Processing
Processing and analyzing continuous streams of data in real-time applications.
Database Systems
Implementing top-k queries in database management systems.
Analytics Platforms
Tracking top performers or metrics in analytics dashboards.
Filtering Systems
Building systems that need to filter and maintain top k elements from a large dataset.