703. Kth Largest Element in a Stream

Prompt

Your task is to design a class that finds thekthlargest element in a stream. It’s important to note that it is thekthlargest element in sorted order, not thekthdistinct element.

The class needs to have 2 components:

  1. KthLargest(int k, int[] nums) — initializes the object with the integer k and the stream of integers nums.
  2. int add(int val) — appends the integer val to the stream and returns the element representing the kth largest element in the stream.

Approach

The naive approach for this problem would be to presort the given nums array (stream) by using your coding language’s built-in sorting method. After sorting the nums array (stream), you can find the kth largest element. The time complexity of this algorithm in the worst case would be dominated by the presorting — O(nlogn). Subsequently, the searching of the kth largest element from the presorted nums array (stream) would be O(n). When analyzing asymptotic time complexity, we would say that our algorithm is O(nlogn) as nlogn scales more than n.

A more efficient approach could be accomplished by utilizing a priority queue, specifically a min-heap. We can convert our nums array (stream) into a heap (for Python, we can conveniently convert an array into a heap using heapify). Then we can check that as long as the length of the nums array (stream) is greater than k, we want to pop from our min-heap until the length of the nums array (stream) is equal to k. By having the length of the nums array (stream) equal to k, we can pop the root element from our min-heap, which would be the kth largest element.

According to the constraints of the problem, it is important to note that we are guaranteed that there will be at least k elements in the array when you search for the kth element. Whenever a test case calls the add method, we need to return the kth largest element as well but this constraint guarantees that when we return the kth largest element by running the add method, we don’t have to worry about running into an error of reading the kth largest element in an array that doesn’t have k elements.

Code

Python

Thank you for reading!

In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.

Discord

If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at cloudiosx@gmail.com

LinkedIn

Portfolio

GitHub

--

--

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
John Kim

John Kim

75 Followers

iOS Developer | Full Stack Developer | Software Engineer | LinkedIn: john-kim-developer | GitHub: cloudiosx | Portfolio: cloudiosx.com