Coder Life
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]
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]

--

--

--

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

Recommended from Medium

Hasura Data and Schema Management APIs

At the origin of C were a school teacher and a string of failures

Angry teacher kicking screen showing “<broken/buggy/code>”

Development process in Omega

Orange France uses Federator.ai

Join DeepPavlov Contributor Program

Commit-ment : Creating your pull requests from Android

Dynamic DataSource Routing: Spring Boot

The art of commenting

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Allie Hsu

Allie Hsu

a tech enthusiast who is keen to develop new skills

More from Medium

Leetcode — 1. Two Sum

Find area of container with most water in O(n) time and O(1) space

LeetCode — Reverse Linked List II

Top Leetcode Browser Extensions