Watch 8 video solutions for Finding MK Average, a hard level problem involving Design, Queue, Heap (Priority Queue). This walkthrough by Happy Coding has 4,863 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two integers, m and k, and a stream of integers. You are tasked to implement a data structure that calculates the MKAverage for the stream.
The MKAverage can be calculated using these steps:
m you should consider the MKAverage to be -1. Otherwise, copy the last m elements of the stream to a separate container.k elements and the largest k elements from the container.Implement the MKAverage class:
MKAverage(int m, int k) Initializes the MKAverage object with an empty stream and the two integers m and k.void addElement(int num) Inserts a new element num into the stream.int calculateMKAverage() Calculates and returns the MKAverage for the current stream rounded down to the nearest integer.
Example 1:
Input
["MKAverage", "addElement", "addElement", "calculateMKAverage", "addElement", "calculateMKAverage", "addElement", "addElement", "addElement", "calculateMKAverage"]
[[3, 1], [3], [1], [], [10], [], [5], [5], [5], []]
Output
[null, null, null, -1, null, 3, null, null, null, 5]
Explanation
MKAverage obj = new MKAverage(3, 1);
obj.addElement(3); // current elements are [3]
obj.addElement(1); // current elements are [3,1]
obj.calculateMKAverage(); // return -1, because m = 3 and only 2 elements exist.
obj.addElement(10); // current elements are [3,1,10]
obj.calculateMKAverage(); // The last 3 elements are [3,1,10].
// After removing smallest and largest 1 element the container will be [3].
// The average of [3] equals 3/1 = 3, return 3
obj.addElement(5); // current elements are [3,1,10,5]
obj.addElement(5); // current elements are [3,1,10,5,5]
obj.addElement(5); // current elements are [3,1,10,5,5,5]
obj.calculateMKAverage(); // The last 3 elements are [5,5,5].
// After removing smallest and largest 1 element the container will be [5].
// The average of [5] equals 5/1 = 5, return 5
Constraints:
3 <= m <= 1051 <= k*2 < m1 <= num <= 105105 calls will be made to addElement and calculateMKAverage.Problem Overview: Design a data structure that processes a stream of integers and returns the MKAverage of the last m elements. The MKAverage removes the k smallest and k largest values from the window and averages the remaining numbers. The structure must support continuous insertions and efficient queries.
Approach 1: Sorting the Window (O(m log m) time, O(m) space)
Maintain a queue containing the last m elements from the stream. Each time you need to compute the MKAverage, copy the elements into an array and sort it. After sorting, ignore the first k and last k elements, then compute the sum of the remaining range and divide by m - 2k. The key idea is brute-force ordering: sorting reveals which values should be removed from both ends. This approach is straightforward and useful for validating logic, but each query costs O(m log m), which becomes expensive when the stream grows. Space complexity stays O(m) because only the sliding window is stored.
Approach 2: Balanced Tree Partitioning (O(log m) time per update, O(m) space)
Use three balanced ordered sets (or multisets) to maintain the smallest k, the largest k, and the middle m - 2k elements. The middle group also tracks its running sum so the MKAverage can be computed in constant time. When a new element arrives, insert it into the appropriate set and rebalance so the sizes remain exactly k, m - 2k, and k. When the window exceeds m, remove the oldest element from whichever set it belongs to and rebalance again. Balanced tree operations like insertion, deletion, and boundary lookup take O(log m). This keeps updates efficient while preserving sorted order. The technique relies heavily on ordered sets and works well for streaming problems in data stream systems.
Recommended for interviews: The balanced tree approach is what interviewers expect for a hard design problem. The sorting solution demonstrates understanding of the MKAverage definition, but it does not scale well. Implementing three ordered partitions with a running sum shows strong control of design patterns and efficient updates in a sliding window.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting the Window | O(m log m) per calculation | O(m) | Simple implementation or small window sizes where performance is not critical |
| Balanced Tree Partitioning | O(log m) per add, O(1) query | O(m) | Optimal for large data streams requiring frequent updates and fast MKAverage queries |