Kth Largest Element in a Stream

Leetcode Problem:

• Kth Largest Element in a Stream

Summary

• Implement a class to track the kth highest test score from applicants in real-time.

Approach

• Use two heaps, a min heap and a max heap, to store the scores
• The max heap stores the k largest scores, and the min heap stores the remaining scores
• When a new score is added, if the min heap is not full, push the score into the min heap
• If the min heap is full and the new score is larger than the smallest score in the min heap, pop the smallest score from the min heap and push the new score into the min heap
• If the new score is smaller than the smallest score in the min heap, push the new score into the max heap
• The kth highest score is the top of the max heap.

Complexity

• O(log n) for push and pop operations, where n is the number of scores.

Explain

• The provided C++ code implements the KthLargest class using two heaps, a min heap and a max heap
• The min heap stores the k largest scores, and the max heap stores the remaining scores
• When a new score is added, if the min heap is not full, push the score into the min heap
• If the min heap is full and the new score is larger than the smallest score in the min heap, pop the smallest score from the min heap and push the new score into the min heap
• If the new score is smaller than the smallest score in the min heap, push the new score into the max heap
• The kth highest score is the top of the max heap
• The time complexity of the push and pop operations is O(log n), where n is the number of scores.

Solution Code:

bool maxCmp(int a, int b){
    return a > b;
}
bool minCmp(int a, int b){
    return a < b;
}
struct _heap{
    int arr[40000];
    int size;
    bool (*cmp)(int , int);
    _heap(){
        size = 1;
    }
    void setCmp(bool (*compare)(int, int)){
        cmp = compare;
    }
    void push(int a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && cmp(arr[idx], arr[idx/2])){
            int tmp = arr[idx];
            arr[idx] = arr[idx/2];
            arr[idx/2] = tmp;
            idx/=2;
        }
    }
    int pop(){
        int ret = arr[1];
        arr[1] = arr[--size];
        int i = 1;
        while(true){
            int j = i * 2;
            if (j >= size) break;
            if (j + 1 < size && cmp(arr[j+1], arr[j])){
                j++;
            }
            if (cmp(arr[j], arr[i])){
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i = j;
            } else {
                break;
            }
        }
        return ret;
    }
    bool empty(){
        return size == 1;
    }
};

class KthLargest {
public:
    _heap minHeap;
    _heap maxHeap;
    int K;
    vector tmp;
    KthLargest(int k, vector& nums) {
        K = k;
        minHeap.setCmp(minCmp);
        maxHeap.setCmp(maxCmp);
        for(int i = 0 ; i < nums.size(); i++){
            maxHeap.push(nums[i]);
        }
        while(k--){
            if (!maxHeap.empty())
                minHeap.push(maxHeap.pop());
        }
    }
    
    int add(int val) {
        if (minHeap.size <= K){
           minHeap.push(val); 
        }
        else if (minHeap.arr[1] < val){
            maxHeap.push(minHeap.pop());
            minHeap.push(val);
        } else {
            maxHeap.push(val);
        }
        
        return minHeap.arr[1];
    }
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */