LeetMotion
Design a class to find the kth largest integer in a stream of values, including duplicates. E.g. the 2nd largest from [1, 2, 3, 3] is 3. The stream is not necessarily sorted.
Implement the following methods:
constructor(int k, int[] nums) Initializes the object given an integer k and the stream of integers nums.int add(int val) Adds the integer val to the stream and returns the kth largest integer in the stream.KthLargest kthLargest = new KthLargest(3, [1, 2, 3, 3]); kthLargest.add(3); // return 3 kthLargest.add(5); // return 3 kthLargest.add(6); // return 3 kthLargest.add(7); // return 5 kthLargest.add(8); // return 6
1 <= k <= 10000 <= nums.length <= 1000-1000 <= nums[i] <= 1000-1000 <= val <= 1000k integers in the stream when you search for the kth integer.Every time a new value comes in, insert it, sort the list, and then pick the element at position len(arr) - k.
Why do it this way? Sorting keeps the numbers in increasing order, so the k-th largest element will always sit at the same index from the end. This method is the most intuitive and easy to understand because sorting directly answers the question of ordering. However, it is very slow because full array sorting happens every time add() is called.
Imagine you have a stack of test scores and you want to know the 3rd highest score. Every time a new test is graded, you insert it into the stack and meticulously re-sort the entire pile from lowest to highest just to check the 3rd one from the top. While accurate, constantly re-sorting the growing pile is exhausting and inefficient!
class KthLargest:
function init(k, nums):
self.k = k
self.arr = nums
function add(val):
self.arr.append(val)
sort(self.arr)
return self.arr[len(self.arr) - self.k]Why do it this way? We realize that to find the k-th largest element, we don't actually care about the relative order of the numbers smaller than our top k. By maintaining a Min-Heap of exactly size k, the heap acts as a "filter" that only holds the top k largest elements seen so far. Because it is a Min-Heap, the smallest of these top k elements sits right at the root, allowing us to fetch the k-th largest instantly in O(1) time without sorting!
Imagine a gaming tournament with only k chairs on the winner's stage. The person sitting in the worst chair (the root of the min-heap) is currently in last place among the winners. When a new player arrives, we compare their score to the person in the worst chair. If the new player has a higher score, the person in the worst chair is kicked out (popped), and the new player takes a seat (pushed), causing the players to naturally rearrange themselves. At any moment, the player in the worst chair is the k-th best player overall!
add(val), insert the new value into the min-heap.class KthLargest:
function init(k, nums):
self.k = k
self.minHeap = nums
heapify(self.minHeap)
while len(self.minHeap) > k:
heappop(self.minHeap)
function add(val):
heappush(self.minHeap, val)
if len(self.minHeap) > self.k:
heappop(self.minHeap)
return self.minHeap[0]A common mistake is using a max-heap. While intuitive to keep largest elements at the top, a max-heap requires storing all elements and extracting max k times for each query. A min-heap of size k directly holds the k-th largest at the root, allowing O(1) retrieval after each insertion.
When using a min-heap, you must remove the smallest element whenever the heap size exceeds k. Failing to do so means the heap grows unbounded, and the root no longer represents the k-th largest element.
Discussion
…