Kth Largest Element in a Stream — LeetCode 703
Difficulty: Easy; Category: Heap
What is Heap?
Heap is a complete binary tree-based data structure. It can be divided into two types:
- Max-heap: the root node must be the greatest one, and all the parents are greater than their children.
- Min-heap: the root node must be the smallest one, and all the parents are smaller than their children.
And python has module heapq to implement the heap data structure:
- heapify(x): transfer a list type value into a heap data structure (min-heap)
- heappush(heap, item): put the item into the heap
- heappop(heap): pop out the smallest value from the heap
- heappushpop(heap, item): put the item into the heap then pop out the smallest value.
The time complexity of heapify() is O(N), heappush() and heappop() art both O(log N). The pop operation is O(log N) because you need to modify the position of another element to maintain the heap.
Note: When the question asks for the kth value, think about using Heap.
Take Example 1 as an example:
In order to get the 3rd largest item in the given list [4,5,8,2], we take the item from the largest to the 3rd one 8 -> 5 -> 4, making them into a considered list. And 2 will never be considered no matter what next item is added.
When an added item comes, determine is it bigger than the smallest number in the considered list or not, if yes, pop out the smallest one in the considered list and push the item into the list.
considered list = [4, 5, 8]
added item = 3
-> no change, return 4
considered list = [4, 5, 8]
added item = 5
-> pop 4, push 5, new considered list become [5, 5, 8], return the new 3rd largest item 5
and so on.
Solution
def __init__(self, k, nums):
"""
:type k: int
:type nums: List[int]
"""
self.k = k
# reverse the list and get largest to kth largest items
self.stream = sorted(nums, reverse=True)[:k]
heapify(self.stream)def add(self, val):
"""
:type val: int
:rtype: int
"""
# if not enough of item, directly push into stream
if len(self.stream) < self.k:
heappush(self.stream, val)
elif self.stream[0] <= val:
heappop(self.stream)
heappush(self.stream, val)
# return the first one in stream,
# which is the kth largest item
return self.stream[0]
