algoadvance

Leetcode 703. Kth Largest Element in a Stream

Problem Statement

You need to design a class to find the Kth largest element in a stream. The class should have the following components:

• A constructor that takes an integer k and an array of integers nums.
• A method int add(int val) that appends the integer val to the stream and returns the element representing the Kth largest element in the stream.

Clarifying Questions

1. Is the input array nums always sorted?
   • No, nums may be unsorted.
2. Can nums be empty?
   • Yes, nums can be empty.
3. Can k be greater than the length of nums?
   • Yes, k can be greater than the length of nums. At any point in time, if the number of elements in the list is less than k, the Kth largest element will be the smallest value (INT_MIN can be used in this implementation).

Strategy

To efficiently manage the Kth largest element in a stream, use a min-heap (priority queue in C++). The heap will have a size of at most k.

• Initialization: Populate the heap with at most k elements from the input array nums.
• Adding Elements: For each new element, if the heap is not full (contains fewer than k elements), push it into the heap. Otherwise, compare it with the smallest element in the min-heap. If it is larger than the smallest (top of the heap), pop the smallest element and insert the new element.

This ensures that the heap contains the k largest elements seen so far, with the smallest of these k elements at the top, which is the Kth largest element.

Code

#include <vector>
#include <queue>
#include <algorithm>

class KthLargest {
private:
    int k;
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    
public:
    KthLargest(int k, std::vector<int>& nums) {
        this->k = k;
        for (int num : nums) {
            add(num);
        }
    }
    
    int add(int val) {
        if (minHeap.size() < k) {
            minHeap.push(val);
        } else if (val > minHeap.top()) {
            minHeap.pop();
            minHeap.push(val);
        }
        return minHeap.top();
    }
};

Time Complexity

• Initialization (KthLargest constructor): O(N log k), where N is the number of elements in the initial array nums. Each insertion into the heap takes O(log k) time.
• Adding Element (add method): O(log k), as we may need to insert the element into the heap or replace the smallest element.

This approach ensures efficient handling of each new element while maintaining the kth largest result.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?