Problem Statement

Implement a class KthLargest to find the kth largest number in a stream. It should have the following methods:

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

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Examples

Example 1:

Input: [KthLargest(3, [1, 2, 3, 4]), add(5), add(2), add(7)]
Output: [null, 3, 3, 4]

Explanation: initial stream = [1, 2, 3, 4], k = 3.
add(5): stream = [1, 2, 3, 4, 5] -> returns 3
add(2): stream = [1, 2, 2, 3, 4, 5] -> returns 3
add(7): stream = [1, 2, 2, 3, 4, 5, 7] -> returns 4

Input: [KthLargest(2, [5, 5, 5, 5], add(2), add(6), add(60)]
Output: [null, 5, 5, 6]

Explanation: initial stream = [5, 5, 5, 5], k = 2.
add(2): stream = [5, 5, 5, 5, 2] -> returns 5
add(6): stream = [5, 5, 5, 5, 2, 6] -> returns 5
add(60): stream = [5, 5, 5, 5, 2, 6, 60] -> returns 6

Different Approaches

1️⃣ Min-Heap (Min-Heap Priority Queue)

Approach:

• We use a min-heap (priority queue) of size k to keep track of the Kth largest element.
• Construction: We iterate through the initial numbers, always keeping the k largest elements in the heap.
• Adding a new element:
  • If the heap has fewer than k elements, insert the new value.
  • If the heap has k elements and the new value is larger than the smallest element (minPQ.top()), replace the smallest element.
  • The root of the heap (minPQ.top()) is always the Kth largest element.

Code:

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class KthLargest {
public:
    int k; // The Kth largest element we need to track
    priority_queue<int, vector<int>, greater<int>> minPQ; // Min-heap to store the top K largest elements

    // Constructor to initialize KthLargest object
    KthLargest(int k, vector<int>& nums) {
        this->k = k;
        // Insert elements into the min-heap
        for (int num : nums) {
            minPQ.push(num); // Push element into the heap
            if (minPQ.size() > k) { // If heap size exceeds k, remove the smallest element
                minPQ.pop();
            }
        }
    }

    // Function to add a new element and return the Kth largest element
    int add(int val) {
        minPQ.push(val); // Insert new element
        if (minPQ.size() > k) { // If heap size exceeds k, remove the smallest element
            minPQ.pop();
        }
        return minPQ.top(); // Return the Kth largest element (smallest in the heap)
    }
};

int main() {
    vector<int> nums = {4, 5, 8, 2};
    KthLargest kthLargest(3, nums); // Find the 3rd largest element

    cout << kthLargest.add(3) << endl;  // 4
    cout << kthLargest.add(5) << endl;  // 5
    cout << kthLargest.add(10) << endl; // 5
    cout << kthLargest.add(9) << endl;  // 8
    cout << kthLargest.add(4) << endl;  // 8

    return 0;
}

Complexity Analysis:

• Time Complexity:
  • Constructor (KthLargest(int k, vector<int>& nums)):
    • We iterate over the entire input array of size n.
    • For each element, we perform a push operation into a min-heap, which takes O(log k) time.
    • If the heap size exceeds k, a pop operation is performed, which also takes O(log k) time.
    • Thus, the overall time complexity for the constructor is O(n log k).
  • add(int val) Method:
    • In this method, we push a new element into the min-heap, taking O(log k) time.
    • If the heap size exceeds k, we remove the smallest element, which takes another O(log k) time.
    • Therefore, the time complexity for each call to add() is O(log k).
• Space Complexity:
  • The min-heap is maintained to store at most k elements at any given time.
  • Apart from the input vector and the heap, no additional space is used.
  • Hence, the total space complexity is O(k).