Kth Largest Element In A Stream Leetcode Problem 703 [Python Solution]

In this guide, we'll dive into solving the LeetCode problem Kth Largest Element In A Stream (Problem 703) with a Python solution.

This problem falls under the category of heap/priority queue and is marked as "Easy." However, you might find it a bit more challenging, but fear not; we'll walk through it step by step.

Problem Overview

The problem requires us to design a class that can find the kth largest element in a stream of numbers.

Here, "stream" means that we can continuously add numbers to the list of elements and still need to find the kth largest element.

Please note that "kth largest" refers to the kth largest element in the sorted order, not the kth distinct element.

We need to implement two main functions:

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

Example 1:

Let's consider an example to understand the problem better:

Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]

Output
[null, 4, 5, 5, 8, 8]

Explanation:
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

Constraints:

1 <= k <= 10^4
0 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
-10^4 <= val <= 10^4
At most 10^4 calls will be made to add.
It is guaranteed that there will be at least k elements in the array when you search for the kth element.

Understanding Constraints

Before we dive into the solution, let's take a closer look at the constraints provided.

Understanding the constraints is crucial when designing an efficient algorithm.

k: This represents the desired order of the kth largest element.

The value of k can range from 1 to 10,000.

nums: This is the initial list of integers provided when the object is initialized.

It can contain anywhere from 0 to 10,000 elements.

val: This is the integer that will be added to the stream, and the function add will return the kth largest element.

The value of val can be between -10,000 and 10,000.

At most 10,000 calls will be made to the add function.

This implies that our solution needs to be efficient and capable of handling a large number of calls.

It is guaranteed that there will be at least k elements in the array when searching for the kth element.

This means that we don't have to handle scenarios where k is greater than the number of elements present in the stream.

Kth Largest Element In a Stream LeetCode Problem Solution

To efficiently solve this problem, we'll use a min-heap data structure.

The min-heap will maintain the k largest elements in the stream, and it will allow us to find the kth largest element with ease.

We'll follow these steps:

Initialize a min-heap with a size of k.
Add the elements from the input nums to the min-heap.
While the size of the min-heap is greater than k, pop the smallest element (as it won't be part of the k largest elements).
When the add function is called, add the new value to the min-heap.
If the size of the min-heap exceeds k, pop the smallest element.
Return the minimum value from the min-heap as the kth largest element.

1. Bruteforce Approach

Before we dive into the efficient approach, let's consider a brute-force solution.

In the brute-force approach, we would maintain a sorted array of elements and search for the kth largest element every time the add function is called.

However, this approach would be highly inefficient, especially for a large number of calls to add.

The time complexity of this approach is O(n), where n is the number of elements in the array.

2. Efficient Approach with Min-Heap

Now, let's implement the efficient solution using a min-heap.

View on GitHub ➹

import heapq  # Import the heapq module

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        # Create a min-heap with k largest integers
        self.minHeap, self.k = nums, k
        heapq.heapify(self.minHeap)
        while len(self.minHeap) &gt; k:
            heapq.heappop(self.minHeap)

    def add(self, val: int) -&gt; int:
        heapq.heappush(self.minHeap, val)  # Add the value to the min-heap
        if len(self.minHeap) &gt; self.k:
            heapq.heappop(self.minHeap)  # Remove the smallest element if size exceeds k
        return self.minHeap[0]  # Return the minimum value from the min-heap

This code defines a class KthLargest, where the constructor initializes the min-heap with k largest elements from the given nums.

The add function adds a new value to the min-heap, ensuring that it contains the k largest elements.

Finally, it returns the kth largest element.

The use of a min-heap allows us to efficiently maintain the k largest elements and find the kth largest element in the stream.

Time and Space Complexity

Let's analyze the time and space complexity of our solution.

Time Complexity

The constructor initializes the min-heap by adding elements from nums.

This step takes O(n * log(k)) time, where n is the number of elements in nums and k is the desired size of the min-heap.

The add function adds a new element to the min-heap.

This operation takes O(log(k)) time.

Overall, the time complexity of our solution for both the constructor and the add function is O(n * log(k)), where n is the number of elements initially provided in nums.

Space Complexity

The space complexity is O(k) since we are using a min-heap of size k to maintain the k largest elements.

Reasoning Behind Our Approach

The choice of using a min-heap

in our solution is crucial for maintaining the k largest elements efficiently.

Min-heaps are excellent for finding the minimum element in constant time and quickly adding elements.

By using a min-heap, we ensure that the k largest elements are always readily available for retrieval.

When we add a new element, we pop the smallest element if the size exceeds k, keeping the min-heap small and efficient.

Conclusion

In this blog post, we tackled the Kth Largest Element In A Stream problem on LeetCode.

We provided an efficient Python solution that leverages a min-heap data structure to maintain the k largest elements in the stream.

Our solution allows for quick retrieval of the kth largest element even as new values are continuously added to the stream.

The time complexity of our solution is O(n * log(k)), and the space complexity is O(k), where n represents the number of elements initially provided in nums, and k is the desired order of the kth largest element.

We hope this guide has been helpful to you, especially if you're new to solving problems involving data structures and algorithms.

If you have any questions, suggestions, or would like further clarification on any part of this solution, please feel free to comment, ask questions, or share your thoughts.

Question Link

Happy coding!