Kth largest element in a stream of running integers
AppleThe problem
Implement a class **KthLargest **to find the k****th **largest **number in a stream. It should have the following methods:
- KthLargest(int k, int [] nums) Initializes the object with the integer k and the initial stream of numbers in nums
- int add(int val) Appends the integer **val **to the stream and returns the k****th largest element in the stream. Note that it is the k****th largest element in the sorted order, not the k****th distinct element.
Input: [KthLargest(3, [1, 2, 3, 4]), add(5), add(2), add(7)] Output: [null, 3, 3, 4] Explanation: initial stream = [1, 2, 3, 4], k = 3. add(5): stream = [1, 2, 3, 4, 5] -> returns 3 add(2): stream = [1, 2, 2, 3, 4, 5] -> returns 3 add(7): stream = [1, 2, 2, 3, 4, 5, 7] -> returns 4
Input: [KthLargest(2, [5, 5, 5, 5], add(2), add(6), add(60)] Output: [null, 5, 5, 6] Explanation: initial stream = [5, 5, 5, 5], k = 2. add(2): stream = [5, 5, 5, 5, 2] -> returns 5 add(6): stream = [5, 5, 5, 5, 2, 6] -> returns 5 add(60): stream = [5, 5, 5, 5, 2, 6, 60] -> returns 6
Input: [KthLargest(4, [5, 1, 2, 7], add(8), add(2), add(6)]
- 1 <= Number of instructions <= 1000
- -104 <= val & all initial values <= 104
- 1 <= k <= 104
- k - 1 <= nums.length <= 103
- The stream will have at least k elements after any add call.
cpp
class KthLargest {
public:
KthLargest(int k, vector<int>& nums) {
}
int add(int val) {
}
};java
class KthLargest {
public KthLargest(int k, int[] nums) {
}
public int add(int val) {
}
}python
class KthLargest:
def __init__(self, k, nums):
def add(self, val):javascript
class KthLargest {
constructor(k, nums) {
}
add(val) {
}
}csharp
class KthLargest
{
public KthLargest(int k, int[] nums)
{
}
public int Add(int val)
{
return 0;
}
}go
type KthLargest struct {
}
func Constructor(k int, nums []int) *KthLargest {
}
func (kl *KthLargest) Add(val int) int {
}Stuck? Show a way to structure it+
- 01Clarify whether output is needed after every insertion
- 02Create a min-heap of capacity k
- 03Push each value and pop when size exceeds k
- 04Read the root when size is k
Reference answer
Then expect these follow-ups
How would you maintain the kth smallest instead?
Tests: follow-up reasoning
What is the time per update?
Tests: complexity analysis
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question