algoadvance

Leetcode 703. Kth Largest Element in a Stream

Problem Statement

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 the KthLargest class:

Clarifying Questions

  1. Can the initial array (nums) be empty?
    • Yes, the initial array can be empty.
  2. What is the range of values for k and the elements in nums?
    • The value of k will be always valid, i.e., 1 ≤ k ≤ length of input stream (number of elements processed so far).
    • The elements in nums and the values added can range from -10^4 to 10^4.
  3. Is it possible to have duplicate numbers in the stream?
    • Yes, duplicates are allowed.
  4. Do we need to handle any concurrency issues?
    • No, assume the operations will be used in a single-threaded environment.

Strategy

To efficiently solve this problem, we will use a minimum heap (priority queue in Java) to keep track of the k largest elements. The smallest element in this heap will be the kth largest element in the stream:

  1. Initialization:
    • Initialize an empty priority queue (min-heap) with a capacity of k.
    • Insert elements from the initial array into the min-heap, maintaining its size at most k.
  2. Adding new elements:
    • Add the new element into the min-heap.
    • If adding this element causes the heap size to exceed k, remove the smallest element from the heap.
    • The root of the heap (the smallest element in the heap) now represents the kth largest element of the stream.

Code

import java.util.PriorityQueue;

class KthLargest {

    private final PriorityQueue<Integer> minHeap;
    private final int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.minHeap = new PriorityQueue<>(k);
        for (int num : nums) {
            add(num);
        }
    }

    public int add(int val) {
        if (minHeap.size() < k) {
            minHeap.offer(val);
        } else if (val > minHeap.peek()) {
            minHeap.poll();
            minHeap.offer(val);
        }
        return minHeap.peek();
    }
}

Time Complexity

  1. Initialization:
    • Building the heap from the initial array takes O(n log k), where n is the length of the initial array nums.
  2. Adding a new element:
    • In the worst case, adding a new element takes O(log k) time due to the heap operations (insert and possibly remove the smallest element).

Thus, each add operation is efficient, and we maintain the k-largest elements in O(log k) time per addition.

If there are any more questions or adjustments needed, feel free to ask!

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