In this article, we will discuss the problem K-th largest Element in a stream, and understand the different methods that can be used to solve the problem efficiently.
Table of content:
- Problem Statement
- Approach 1: Sorting the Array
- Approach 2: Using min-heap
We will dive into the problem now.
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.
KthLargest(int k, int nums)Initializes the object with the integer
kand the stream of integers
int add(int val)Appends the integer
valto the stream and returns the element representing the
kthlargest element in the stream.
Let us understand the question first.
We are given a stream of numbers and we need to find the Kth largest value in that stream.
But, what does Kth largest Value mean?
Consider this example
In the above array, there are 10 integers lets try to find the 4th largest value in this array. So let's just arrange the elements of the array in descending order and find the fourth value. Yes, that's the 4th largest value in the array.
Similarly, we are required to find the kth largest value in a given stream of integers.
We will solve this problem in two methods.
- By sorting the array
- Using Min heap
Approach 1: Sorting the Array
In this method, we sort the stream of integers after adding a new value to it each time and then we access the required largest element and return it.
- Add the new element into the array
- sort the array
- Find the Kth element from the last of the sorted array and return it.
class KthLargest: def __init__(self, k: int, nums: List[int]): self.k = k self.nums = nums def add(self, val: int) -> int: self.nums.append(val) return sorted(self.nums)[-1 * self.k]
You may wonder why we are implementing this through a class? It is because we are dealing with a stream of numbers hence using a class makes it convenient for us to add the numbers to the stream and find the Kth largest number in it.
We can see two methods in this class, the first
init method is used to initialize the class with the initial stream of numbers
nums and the value of
The second method is where we find the Kth largest number in the stream. This method takes a number
val which is to be added to the stream. And then we append the integer
val to the stream. And then we sort the elements in the array
nums, now we access the kth element from the end of the array which will give us the Kth largest element in the array, and we return it.
Complexity of this method
In this method, we are sorting the array each time, thus the time complexity of this method is
O(n), where n is the number of elements in the array.
The space complexity of the algorithm is
The runtime and memory for solving the problem using this method are given below.
We can see that this runtime is extremely high and sometimes it may exceed the time limit of the problem too.
Approach 2: Using min-heap
Using min-heap is a much more efficient way to solve the problem, we will see that in a bit. But, before we start solving the problem using a min-heap, let's quickly recall what a min-heap is.
A min-heap is a binary tree data structure, where the parent node is smaller than its child nodes.
The above image is an example of a min-heap.
The most important thing to understand in min-heap is that the child nodes are greater than the parent node. As a result of this, the root node holds the smallest value of the heap and the end node holds the largest value of the heap.
But how can we use this min-heap to solve our problem? In our question, we are asked to return the Kth largest number in the stream, which means there are k-1 numbers larger than our answer, and the rest of the numbers which are smaller than the Kth largest number do not matter.
So, we create a min-heap of size
k i.e. containing the
k largest elements of the stream. So the root node will always have our Kth Largest element of the stream. Thus, the only thing we need to do is keep the min-heap updated with K largest numbers and we can retrieve our Kth largest number quickly from the root node, let's see how we can do this with the code.
- Create a class for the min-heap data structure ( here built-in functions are used to do the heap operations )
- Create a method to initialize the min-heap
- Create a method to push an element into the min-heap
- Create a method to return the root node i.e. the K the largest number
- Get the input array and the value of k.
- Update the min-heap with the values of the input array
- Then get the values to be added into the stream
- Return the root node of the min-heap
from heapq import heappush , heappop class minHeap: # Initializes the heap def __init__(self, k): self.heap =  self.size = k # a method to push elements into the min heap def push(self, val): # pushs the elements into the minHeap if the heap size is less than k if len(self.heap) < self.size : heappush(self.heap,val) # push the element into the heap if it is greater than the root node elif val > self.heap : heappop(self.heap) heappush(self.heap,val) # a method to return the root node def ans(self): return self.heap class KthLargest: def __init__(self, k: int, nums: list[int]): self.nums = minHeap(k) self.k = k for i in nums: self.nums.push(i) # a method to add elements into the stream and return the Kth largest value def add(self, val: int) -> int: self.nums.push(val) return self.nums.ans()
Phew, I know this code looks a bit messy, but don't worry let's break it down and we will understand everything.
First, let's deal with the
minHeap class. This class has 3 methods,
- The first method initializes the minHeap class with an array to store the values of the heap and the maximum size of the heap i.e. the value of
- The second method
push()is used to push the elements into the min-heap and keep the min-heap updated with the K largest numbers of the stream.
- The first
ifstatement pushes anything into the heap if the size of the heap is less than
elifstatement checks if the element passed into the stream is greater than the root node i.e. the kth largest element so far, if it is greater than it, it pops out the element in the root node and pushes the new element into it. Doing so the min-heap gets updated and the new Kth largest number will be at the root node.
- The first
Note: If you don't understand how the pushing and popping of elements in the min-heap take place, feel free to refer to this article.
- The third method
ans()is a simple method that returns the root node of the min-heap.
Now coming to the
KthLargest Class, since the min-heap class does all the calculations we need to find the kth largest number in the stream, we just need to pass values into the min-heap and return the answer in this Class
The first method initializes the
KthLargest class with the value of
k and the min-heap that will be used to find the kth largest number in the stream. And then we use a for loop to add the initial elements of the stream into the min-heap.
The second method
add() is used to get the new elements of the stream and return the Kth largest element in the stream. Here, we just use the
push() method from the min-heap class to update the min-heap with the new number.
And then finally, we use the
ans() method to return the root node i.e. the Kth largest element in the stream.
Complexity of the algorithm
You may wonder why to go through the pain of creating a min-heap and pushing elements to it, while we can just sort the array stream and return the Kth largest element.
The reason is speed. The time complexity of the operations in a min-heap is
O(log k), Thus reducing the time taken for finding the Kth largest value exponentially and this makes our algorithm really fast.
The space complexity of this approach is
The runtime and memory of this approach is given below
When we compare this runtime with the runtime of the brute force approach we can see that this is nearly 70x times faster than that.
Every problem can be solved in multiple ways, but always opt for the one that has the best time & space complexity and is faster than the other solutions. With this article at OpenGenus, you must have the complete knowledge of finding the k-th largest element in a stream of numbers.