703. Kth Largest Element in a Stream LeetCode Solution

In this guide, you will get 703. Kth Largest Element in a Stream LeetCode Solution with the best time and space complexity. The solution to Kth Largest Element in a Stream problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Kth Largest Element in a Stream solution in C++
Kth Largest Element in a Stream solution in Java
Kth Largest Element in a Stream solution in Python
Additional Resources

703. Kth Largest Element in a Stream LeetCode Solution image

Problem Statement of Kth Largest Element in a Stream

You are part of a university admissions office and need to keep track of the kth highest test score from applicants in real-time. This helps to determine cut-off marks for interviews and admissions dynamically as new applicants submit their scores.
You are tasked to implement a class which, for a given integer k, maintains a stream of test scores and continuously returns the kth highest test score after a new score has been submitted. More specifically, we are looking for the kth highest score in the sorted list of all scores.
Implement the KthLargest class:

KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of test scores nums.
int add(int val) Adds a new test score val to the stream and returns the element representing the kth largest element in the pool of test scores so far.

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”, “add”, “add”]
[[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]
Output: [null, 7, 7, 7, 8]
Explanation:
KthLargest kthLargest = new KthLargest(4, [7, 7, 7, 7, 8, 3]);
kthLargest.add(2); // return 7
kthLargest.add(10); // return 7
kthLargest.add(9); // return 7
kthLargest.add(9); // return 8

Constraints:

0 <= nums.length <= 104
1 <= k <= nums.length + 1
-104 <= nums[i] <= 104
-104 <= val <= 104
At most 104 calls will be made to add.

Complexity Analysis

Time Complexity: O(n\log k)
Space Complexity: O(k)

703. Kth Largest Element in a Stream LeetCode Solution in C++

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();
  }
};
/* code provided by PROGIEZ */

703. Kth Largest Element in a Stream LeetCode Solution in Java

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();
  }
}
// code provided by PROGIEZ