Solution: Finding MK Average

Explore how to design a custom data structure that calculates MK Average from a data stream by maintaining three balanced sorted lists. Understand insertion, removal, and rebalancing techniques to achieve efficient updates and quick average computation, preparing you for interview problems involving complex data stream processing.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

Statement

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:

Stream length check: If the stream contains fewer than m elements, return -1 as the MK Average.
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.
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 ...