Leetcode #: 703
Name: Kth Largest Element in a Stream
Difficulty: Easy
Companies asked: Amazon, Tesla
Url: https://leetcode.com/problems/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:
- 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.
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
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.
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
