Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

703. Kth Largest Element in a Stream

Time: $O(n\log k)$

Space: $O(k)$

			


class KthLargest {
 public:
  KthLargest(int k, vector<int>& nums) : k(k) {
    for (const int num : nums)
      heapify(num);
  }

  int add(int val) {
    heapify(val);
    return minHeap.top();
  }

 private:
  const int k;
  priority_queue<int, vector<int>, greater<>> minHeap;

  void heapify(int val) {
    minHeap.push(val);
    if (minHeap.size() > k)
      minHeap.pop();
  }
};




			


class KthLargest {
  public KthLargest(int k, int[] nums) {
    this.k = k;
    for (final int num : nums)
      heapify(num);
  }

  public int add(int val) {
    heapify(val);
    return minHeap.peek();
  }

  private final int k;
  private Queue<Integer> minHeap = new PriorityQueue<>();

  private void heapify(int val) {
    minHeap.offer(val);
    if (minHeap.size() > k)
      minHeap.poll();
  }
}