Kth Largest Element in a Stream
Problem Description
You are part of a university admissions office and need to keep track of the kth highest test score from applicants in real-time. This helps to determine cut-off marks for interviews and admissions dynamically as new applicants submit their scores.
You are tasked to implement a class which, for a given integer k, maintains a stream of test scores and continuously returns the kth highest test score after a new score has been submitted. More specifically, we are looking for the kth highest score in the sorted list of all scores.
Implement the KthLargest class:
KthLargest(int k, int[] nums)Initializes the object with the integerkand the stream of test scoresnums.int add(int val)Adds a new test scorevalto the stream and returns the element representing the kth largest element in the pool of test scores so far.
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]
Explanation:
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]
Explanation:
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.
Solve it on LeetCode
Approaches
1. Brute Force with Sorting
Intuition:
For each addition of a new element into the stream, we can sort the elements and fetch the k-th largest element directly. This approach is straightforward but inefficient for larger inputs.
Steps:
- Maintain a list of numbers that we will continually update as new numbers are added.
- Every time a new number is added, insert it into the list.
- Sort the list in descending order.
- Retrieve the k-th element from the sorted list.
Code:
- Time Complexity:
O(n log n)for sorting the list each time a new element is added (wherenis the number of elements in the list). - Space Complexity:
O(n)for storing the elements in a list.
2. Sorted List
Intuition:
Maintain a sorted list at all times and ensure the list is sorted with each new insertion. This results in better time complexity than re-sorting the entire list.
Steps:
- Maintain a list of numbers, sorted after each insertion.
- Use binary search to find the position where the new element should be inserted to keep the list sorted.
- After insertion, directly access the k-th largest element.
Code:
- Time Complexity:
O(k)for maintaining a sorted list by binary search and insertion. - Space Complexity:
O(n)for storing the stream of numbers.
3. Min-Heap (Optimal)
Intuition:
Use a min-heap of size k to efficiently manage the k-th largest element. The min-heap will allow the smallest element to be on top, ensuring we can easily access the k-th largest element by maintaining heap size.
Steps:
- Use a PriorityQueue (min-heap) of size
k. - Iterate over the initial list and add each element to the heap.
- If the heap exceeds size
k, remove the smallest element (top of the heap). - For a new addition, add the element and ensure the heap does not exceed size
k. - The top element of the heap will be the k-th largest element.
Code:
- Time Complexity:
O(log k)for each addition (heap insertion and adjustment). - Space Complexity:
O(k)for maintaining the heap of sizek.