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.

Implement KthLargest class:

• KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of numbers nums.
• int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

Example 1:

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

Example 2:

Input: ["KthLargest", "add", "add"] [[1, []], [-3], [-2]] Output: [null, -3, -2]

Explanation: KthLargest kthLargest = new KthLargest(1, []); kthLargest.add(-3); // return -3 kthLargest.add(-2); // return -2

Steps

1. Initialization: The constructor initializes a min-heap of size k with the initial numbers. A min-heap is chosen because we want the smallest of the largest k elements readily available.

2. Adding a Number: When a new number val is added:

   • If the heap size is less than k, add val to the heap.
   • If the heap size is equal to k and val is greater than the smallest element in the heap (heap's root), replace the root with val and heapify (re-organize the heap to maintain the min-heap property).
   • If the heap size is equal to k and val is less than or equal to the smallest element, do nothing.

3. Returning the Kth Largest: The root of the min-heap always holds the kth largest element.

Explanation

The efficiency of this approach comes from using a min-heap. A min-heap allows for efficient retrieval of the smallest element (O(1)) and efficient insertion/deletion (O(log k)). Therefore, adding a new element and finding the kth largest element are both O(log k) operations. Using a simple array or list would require sorting the entire list every time a number is added, resulting in O(n log n) complexity where n is the number of elements.

Code

using System;
using System.Collections.Generic;

public class KthLargest
{
    private int k;
    private PriorityQueue<int, int> minHeap; // Use a min-heap to store the k largest elements

    public KthLargest(int k, int[] nums)
    {
        this.k = k;
        minHeap = new PriorityQueue<int, int>();

        foreach (int num in nums)
        {
            Add(num);
        }
    }

    public int Add(int val)
    {
        minHeap.Enqueue(val, val); // We use value as both priority and value for simplicity
        if (minHeap.Count > k)
        {
            minHeap.Dequeue(); // Remove the smallest element if the heap size exceeds k
        }
        return minHeap.Peek(); // Return the kth largest element (root of the min-heap)

    }
}

Complexity

• Time Complexity:

  • KthLargest(int k, int[] nums): O(n log k), where n is the length of nums. This is because of the heap creation.
  • add(int val): O(log k). Adding an element and maintaining the heap property takes logarithmic time.

• Space Complexity: O(k) to store the min-heap. The space used is proportional to k, regardless of the input stream size.