Finding Mk Average - Leetcode Solution

The problem statement for the Finding Mk Average problem on LeetCode is as follows:

Design a data structure that receives a stream of integers, creates and maintains a sorted list of the last M integers (from the stream), and has a method to return the median of the last K integers (from the sorted list). The constructor of the data structure receives an integer, M, representing the number of the last elements the data structure keeps for every new integer. It also receives an integer, K, representing the number of elements we need to calculate the median.

The data structure should have a method named addElement that receives an integer, val, and adds it to the data structure. The data structure should also have a method named calculateMKAverage that returns the median of the last K elements of the sorted list of the last M input elements. If there are less than K elements in the sorted list, MKAverage returns -1.

Solution:

To solve the given problem, we need to implement a data structure that can receive data in a stream and calculate the median of a sub-array of the last M elements. One approach to solve such types of problems is to use a circular buffer or a deque. We can implement the MKAverage algorithm using a deque data structure with the following steps:

1. Create a deque with a fixed size of M to store and maintain the last M integers.
2. Create two priority queues, left, and right, to store the integers in sorted order.
3. Implement a function to add a new integer to the deque. If the deque is full, remove the oldest integer to maintain the size of M.
4. Whenever a new integer is added or an integer is removed from the deque, adjust the two priority queues based on the new integers.
5. Implement a function to find the median of the last K integers. If K is greater than the current size of the deque, return -1.
6. If K is smaller than or equal to the current size of the deque, pop and push elements from the left and right priority queues until the size of the deque becomes equal to K.
7. If K is even, the median is the average of the two central elements. If K is odd, the median element is the middle element.

Here is the code implementation of the above algorithm:

class MKAverage {
private:
    deque<int> window;
    priority_queue<int> left;
    priority_queue<int, vector<int>, greater<int>> right;
    long m, k, sum;
public:
    MKAverage(int m, int k) {
        this->m = m;
        this->k = k;
        this->sum = 0;
    }

    void addElement(int num) {
        window.push_back(num);
        sum += num;
        if (window.size() > m) {
            sum -= window.front();
            window.pop_front();
        }

        if (left.empty() || num <= left.top())
            left.push(num);
        else
            right.push(num);
        
        if (left.size() > (m - k) ) {
            sum -= left.top();
            right.push(left.top());
            left.pop();
        }
        else if (right.size() > k) {
            sum -= right.top();
            left.push(right.top());
            right.pop();
        }
    }

    int calculateMKAverage() {
        if (window.size() < k)
            return -1;
        long res_sum = sum;
        if (left.size() == (m - k))
            res_sum -= left.top() * (m - k);
        else
            res_sum -= right.top() * k;
        return res_sum / k;
    }
};

The implementation of the MKAverage class includes a constructor and two methods: addElement and calculateMKAverage. The constructor initializes the size of the deque and priority queues, and the sum variable holds the sum of the current window.

The addElement method adds a new element to the deque and updates the sum variable. If the size of the deque exceeds M, it removes the oldest element. Then, it maintains the left and right priority queues based on the new element and the current size. If the size of the left queue exceeds (M-k), it moves the top element to the right queue to balance the sizes. Similarly, if the size of the right queue exceeds k, it moves the top element to the left queue to balance the sizes.

The calculateMKAverage method calculates the median of the last K integers added to the deque. If the size of the deque is less than K, it returns -1. Otherwise, it calculates the sum of the integers in the window after removing the top elements from the left or right queue. Finally, it returns the average of the remaining K integers.

This implementation has a time complexity of O(log k) for adding a new integer to the deque (due to the use of priority queues) and a time complexity of O(1) for calculating the median. The space complexity is O(M) to store the deque and priority queues.

1