703. Kth Largest Element in a Stream #309
Answered
by
mah-shamim
mah-shamim
asked this question in
Q&A
-
|
Topics: Design a class to find the Implement
Example 1:
Example 2:
Constraints:
|
Beta Was this translation helpful? Give feedback.
Answered by
mah-shamim
Aug 12, 2024
Replies: 1 comment 2 replies
-
|
We can use a min-heap data structure. Here’s a step-by-step guide to implementing the
Here’s the PHP code to implement the <?php
class KthLargest {
private $minHeap;
private $k;
public function __construct($k, $nums) {
$this->k = $k;
$this->minHeap = new SplMinHeap();
foreach ($nums as $num) {
$this->add($num);
}
}
public function add($val) {
if ($this->minHeap->count() < $this->k) {
$this->minHeap->insert($val);
} elseif ($val > $this->minHeap->top()) {
$this->minHeap->extract();
$this->minHeap->insert($val);
}
return $this->minHeap->top();
}
}
// Example Usage:
$kthLargest = new KthLargest(3, [4, 5, 8, 2]);
echo $kthLargest->add(3) . "\n"; // returns 4
echo $kthLargest->add(5) . "\n"; // returns 5
echo $kthLargest->add(10) . "\n"; // returns 5
echo $kthLargest->add(9) . "\n"; // returns 8
echo $kthLargest->add(4) . "\n"; // returns 8
?>Explanation:
This approach ensures that we efficiently keep track of the k-th largest element with each insertion into the stream, maintaining an O(log k) complexity for insertion operations due to heap operations. |
Beta Was this translation helpful? Give feedback.
2 replies
-
|
Thanks for solving the problem of "Kth Largest Element in a Stream" |
Beta Was this translation helpful? Give feedback.
-
|
Thanks |
Beta Was this translation helpful? Give feedback.
Answer selected by
basharul-siddike
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
We can use a min-heap data structure. Here’s a step-by-step guide to implementing the
KthLargestclass using PHP:Min-Heap Data Structure: We will maintain a min-heap (priority queue) of size
k. The root of this heap will always give us the k-th largest element.Initialization: During initialization, we will add the first
kelements of the stream to the min-heap. For any additional elements, we will compare each new element with the smallest element in the heap (the root). If the new element is larger, we replace the smallest element with this new element and adjust the heap to maintain the k size.Adding Elements: Each time an element is added to the stream, we use the same process…