Published in

Coder Life

# 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:

1. Max-heap: the root node must be the greatest one, and all the parents are greater than their children.
2. 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]
-> no change, return 4

considered list = [4, 5, 8]
-> 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]`

--

--

--

## More from Coder Life

A place that share all value skills and techniques I learned in development.

## Allie Hsu

a tech enthusiast who is keen to develop new skills