LeetCode 703. Kth Largest Element in a Stream [heap] Java

Source: https://leetcode.com/problems/kth-largest-element-in-a-stream/

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 KthLargest 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 KthLargest.add, return the element representing the kth largest element in the stream.

Example:

int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
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

Note: 
You may assume that nums‘ length ≥ k-1 and k ≥ 1.

Solution 1: A max-heap and a min-heap

Try to solve this kind of problem, you can easily think about the heap, but this problem is a little complex. First I build a max-heap, so I can get the initial kth largest element.

Then when we add a number small or equal than the current kth largest element, it will cause nothing, we can just ignore it. When it is larger than the current kth largest element, the original kth largest element need be removed, and the new number should add to the top-k numbers to compare which is the smallest.

So we can use a min-heap save the top-k numbers. If the new number is smaller, don’t touch min-heap, just output the top of the heap.

If the new number is larger, we use it to replace the top of the heap, and minHeapify(1), then we can ensure the top of the heap is the kth largest element, so then we output it.

So the code of the constructor like this:

Method add:

And we add a method replaceTop to min-heap:

Runtime: 61 ms, faster than 66.06% of Java online submissions for Kth Largest Element in a Stream.

Memory Usage: 48.1 MB, less than 42.98% of Java online submissions for Kth Largest Element in a Stream.

Solution 2: One min-heap

After thinking about solution1, we found the max-heap is not necessary. One min-heap can solve this problem too. First, we create an array size is k, make every element in this array is Integer.MIN_VALUE. Then we make it a min-heap, use the add method to add all elements in. We will find out this heap is the top-k elements already. And add more numbers will not change this property. The time complexity is not much different from solution 1. But the code is simpler and easier. We don’t need to change the add and the replaceTop method, we only need a new constructor.

Github: https://github.com/tinyfool/leetcode/tree/master/src/p0703

Want to know more details of heap and heapsort, check my post:Heap and Heap-Sort algorithm.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.