Kth Largest Element in a Stream easy

Problem Statement

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.

Your KthLargest class will have a constructor which accepts an integer k and an integer array nums, which contains initial elements from the stream. For each call to the method add, return the kth largest element in the stream.

Example 1:

int k = 3;
int[] nums = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, nums);
kthLargest.add(3);   // returns 4
kthLargest.add(5);   // returns 5
kthLargest.add(10);  // returns 5
kthLargest.add(9);   // returns 8
kthLargest.add(4);   // returns 8

Example 2:

int k = 1;
int[] nums = [];
KthLargest kthLargest = new KthLargest(1, nums);
kthLargest.add(6);   // returns 6
kthLargest.add(10);  // returns 10
kthLargest.add(-1);  // returns 10

Steps:

1. Import heapq: We'll use Python's heapq module for efficient heap-based operations.
2. Constructor (__init__): Initialize a min-heap with the initial nums array. We use a min-heap because we want the smallest of the largest k elements readily available. We only need to keep track of the k largest elements.
3. add method: Add the new element to the heap. If the heap size exceeds k, pop the smallest element (root of the min-heap) to maintain the heap size. The root of the min-heap will always be the kth largest element.

Explanation:

The solution leverages the properties of a min-heap data structure. A min-heap efficiently maintains the smallest element at the root. By keeping a min-heap of size k, the root always represents the kth largest element seen so far. When a new element is added, if it's larger than the kth largest (root), it's added and the smallest element is popped, ensuring we retain only the k largest elements.

Code:

import heapq

class KthLargest:

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

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

Complexity:

• Time Complexity:

  • __init__: O(N log k), where N is the length of nums. Building the heap takes at most O(k log k) time. Initializing the heap takes O(N log k) time in the worst case.
  • add: O(log k). Adding and removing elements from a heap of size k takes O(log k) time.

• Space Complexity: O(k). The heap stores at most k elements.