You are given two integers, m and k, and a stream of integers. Your task is to design and implement a data structure that efficiently calculates the MK Average for the stream.

To compute the MK Average, follow these steps:

1. Stream length check: If the stream contains fewer than m elements, return -1 as the MK Average.

2. Window selection: Otherwise, copy the last m elements of the stream to a separate container and remove the smallest k elements and the largest k elements from the container.

3. Average calculation: Calculate the average of the remaining elements (rounded down to the nearest integer).

Implement the MKAverage class

• MKAverage(int m, int k): Initializes the object with integers m and k and an empty stream.

• void addElement(int num): Adds the integer num to the stream.

• int calculateMKAverage(): Returns the current MK Average for the stream as described above, or -1 if the stream contains fewer than m elements.

Constraints:

• $3 <=$ m $<= 10^5$

• $1 <$ k*2 $< m$

• $1 <=$ num $<= 10^5$

• $10^3$ calls will be made to addElement and calculateMKAverage, at most.

The algorithm is designed to maintain a moving window of the last m integers from a data stream and compute the average of the middle m - 2k elements, discarding the smallest and largest k elements. It achieves this by using a deque (window) to store elements in insertion order, and three sorted lists—low, mid, and high—to track the smallest k, middle m - 2k, and largest k elements, respectively. Only the mid values contribute to the final average, and their running total is maintained through a variable called mid sum for constant-time average computation.

When a new element is added and the total count is still less than m, it is placed into mid by inserting it at the correct position to keep mid sorted, contributing to mid sum. Once the window reaches size m, a copy of the elements is taken from the deque, sorted into a new list, and then divided into low, mid, and high segments, with mid sum initialized to the sum of the mid list.

For all subsequent insertions:

• The oldest element is removed from the window and also from one of the three lists (low, mid, or high) using binary search to locate its position.

• If it is removed from mid, mid sum is updated accordingly.

• The new element is then inserted into the correct list based on its value relative to the largest element in low or the smallest in high.

• If it lies between these boundaries, it goes into the mid and contributes to the mid sum.

After insertion and deletion, the algorithm rebalances the three lists:

• If low exceeds size k, its largest value is moved to mid and added to mid sum. If smaller than k, the smallest value from mid is moved to low and subtracted from mid sum.

• The same rebalancing logic is applied between mid and high: if high is too large, its smallest element is moved to mid and added to mid sum; if it is too small, the largest value from mid is moved to high and subtracted from the mid sum.

Finally, the average calculation method returns -1 if fewer than m elements have been added; otherwise, it returns the integer division of mid sum by (m - 2k), providing the required MK Average.

Using three lists is more efficient because each list has a fixed role: one always holds the smallest k elements, one the largest k, and one the middle values that matter for the average. This separation makes it easy to know exactly where an element belongs when adding or removing numbers, without scanning or reshuffling the entire window. It also allows the running sum of the middle values to be updated directly whenever elements move in or out. In contrast, using a single list with boundary pointers would require more work to maintain order and update the middle sum, making the process slower and more complicated.

The steps of the algorithm are as follows:

1. Constructor: The constructor initializes:

   1. The window size m and cutoff k.

   2. A deque (window) to hold the most recent m numbers.

   3. Three sorted lists: low (k smallest), mid (middle m-2k), and high (k largest).

   4. An integer mid_sum to quickly compute the sum of the middle section.

2. addElement(num):

   1. If the window is not yet full (len(window) < m):

      1. Simply insert num into mid using bisect.insort.

      2. Increment mid_sum by num.

   2. If the window just reached full size (len(window) == m):

      1. Copy and sort the m elements of the window in nums, then partition into three ranges: low = first k (smallest), mid = next m−2k, high = last k (largest).

      2. Calculate mid_sum as the sum of the mid list.

   3. If the window is already full (len(window) > m):

      1. Removal of the oldest element: Remove the oldest element old from the window and identify which list (low, mid, or high) it belongs to using binary search. Once located, remove it from the respective list and, if it was in mid, subtract its value from mid_sum.

      2. Insertion of the new element: Insert a number num into the correct list, compare it against the boundary values of the current partitions. If it’s less than or equal to the largest element in low, insert it into low; if it’s greater than or equal to the smallest in high, insert it into high. Otherwise, place it in mid and update mid_sum accordingly.

      3. Rebalancing: After inserting or removing elements, the lists low, mid, and high might become unbalanced. The goal is to ensure that: low always contains exactly k smallest elements, high always contains exactly k largest elements, and mid contains the remaining m - 2k elements.

         1. Rebalancing low:

            1. If low contains more than k elements, remove its largest element (the last item), insert it into mid while maintaining sorted order, and add its value to mid_sum.

            2. If low contains fewer than k elements, remove the smallest element (the first item) from mid, insert it into low while maintaining sorted order, and subtract its value from mid_sum.

         2. Rebalancing high:

            1. If high contains more than k elements, remove its smallest element (the first item), insert it into mid while maintaining sorted order, and add its value to mid_sum.

            2. If high contains fewer than k elements, remove the largest element (the last item) from mid, insert it into high while maintaining sorted order, and subtract its value from mid_sum.

3. calculateMKAverage():

   1. If there are not yet m elements, return -1.

   2. Otherwise, return the integer division of mid_sum by (m-2k), which is the number of elements in the mid list.

Let’s look at the following illustration to get a better understanding of the solution: