Skip to main content

Kth Largest Element in a Stream

Problem​

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 integers nums.
  • int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

Solution Approach​

Expected Time complexity: O(n)O(n)

Click - to see solution code
class KthLargest {
    vector<int> num;
    int k;
    int n;

   public:
    KthLargest(int kk, vector<int>& nums) {
        this->num = nums;
        this->k = kk;
        this->n = nums.size();
    }

    int add(int val) {
        num.push_back(val);
        n++;
        nth_element(num.begin(), num.begin() + n - k, num.end());
        return num[n - k];
    }
};