algoadvance

Clarifying Questions:

1. Is the stream finite, and what are its characteristics (size, range of values)?
2. Can elements be added dynamically to the stream?
3. How frequently do we need to query the Kth largest element?
4. What is the acceptable time complexity for adding elements and querying the Kth largest element?

Usually, the problem description on platforms like LeetCode will provide sufficient details that:

• You will be given an initial list of integers.
• You need to design a class that allows adding new integers to the stream.
• Each addition operation will also provide the Kth largest element in the stream.

Strategy:

We will use a min-heap (priority queue) of fixed size k to efficiently track the Kth largest element.

1. Initialization:
   • Initialize a min-heap with the first k elements.
   • If there are fewer than k elements initially, initialize the heap with all elements.
2. Adding New Elements:
   • If the heap contains fewer than k elements, add the new element directly to the heap.
   • Otherwise, compare the new element with the smallest element (root of the heap):
     • If the new element is larger, replace the smallest element with the new element.
3. Fetching the Kth Largest Element:
   • The Kth largest element will always be the root of the min-heap.

Code:

import heapq

class KthLargest:

    def __init__(self, k: int, nums: list):
        self.k = k
        self.min_heap = []
        for num in nums:
            self.add(num)

    def add(self, val: int) -> int:
        if len(self.min_heap) < self.k:
            heapq.heappush(self.min_heap, val)
        elif val > self.min_heap[0]:
            heapq.heapreplace(self.min_heap, val)
        
        return self.min_heap[0]

# Example usage:
# kthLargest = KthLargest(3, [4, 5, 8, 2])
# print(kthLargest.add(3))  # returns 4
# print(kthLargest.add(5))  # returns 5
# print(kthLargest.add(10))  # returns 5
# print(kthLargest.add(9))  # returns 8
# print(kthLargest.add(4))  # returns 8

Time Complexity:

1. Initialization:
   • Building the initial heap with n elements where n is the number of elements: O(n log k).
2. Adding an Element:
   • Adding an element to the heap of size k: O(log k).
3. Fetching the Kth Largest Element:
   • Fetching the minimum element in the heap (Kth largest element): O(1).

Summary:

• The KthLargest class maintains a min-heap of size k to keep track of the Kth largest element efficiently.
• The add method ensures we maintain the correct heap size and immediately provide the Kth largest element after each insertion.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?