Leetcode Daily Question 12/08/2024 - 703. Kth Largest Element in a Stream

Problem Description:

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. Implement KthLargest class: KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums. int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

import heapq
class KthLargest:
  def __init__(self, k: int, nums: List[int]):
    self.k = k
    self.nums = nums
    heapq.heapify(self.nums)
    while len(self.nums) > self.k:
      heapq.heappop(self.nums)
      
  def add(self, val: int):
    heapq.heappush(self.nums, val)
    if len(self.nums) > self.k:
      heapq.heappop(self.nums)
      
    return self.nums[0]

Explanation:

There are plenty of ways to find the kth largest element in an array. The most naive way is probably to use a stack or a deque. However, this result in an inefficient use of space and time, O(n^2).

Another way we could do this is to use a minimum heap. A heap takes form of a complete binary tree. In other words, a binary tree that is filled on every level except from possibly the last, which is filled from left to right.

As an example, the following tree is a min heap.

1
       / \
      3   6
     / \ / \
    5  9 8  10
      
node '1' < '3', '6', its left and right children
node '3' < '5', '9'
node '6' < '8', '10

This is useful as the first element to be removed as we traverse the tree top down, is always the smallest element of the tree.

We can utilise the inbuilt heapq module of python. The main methods we would use are:
- heappop(min_heap) : this removes the root of the tree and rebuilt the tree.
- heappush(min_heap, value) : this pushes a new value into the tree structure and shuffles the elemtns as required.
- heapify(arr) : this makes an array into a min heap structure by default.

To achieve maximum time efficiency, we first make sure that our min_heap only has k elements in it. This means we only have to deal with the new element that will be added into the heap. Making the operation O(log k). (Space complexity O(n), where n is len(arr)).

The kth largest element in the heap is then the top element of the heap.

import heapq
class kthLargest:
  def __init__(self, k: int, nums: List[int]):
  	self.k = k
  	self.nums = nums
    heapq.heapify(self.nums)
    while len(self.nums) > self.k:
      heapq.heappop(self.nums)
      
  def add(self, val:int):
    heapq.heappush(self.nums, val)
    if len(self.nums) > self.k:
      heapq.heappop(self.nums)
   	return self.nums[0]