Distinct Numbers in Window

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(nlogn)$

Click - to see solution code

C++

vector<int> Solution::dNums(vector<int> &A, int B) {
    map<int, int> mp;
    int n = A.size();
    for (int i = 0; i < B; i++) {
        mp[A[i]]++;
    }
    vector<int> ans;
    ans.push_back(mp.size());
    for (int j = B; j < n; j++) {
        mp[A[j]]++;
        mp[A[j - B]]--;
        if (mp[A[j - B]] == 0) {
            mp.erase(A[j - B]);
        }
        ans.push_back(mp.size());
    }
    return ans;
}