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.
This approach uses a sliding window to keep track of the last m elements inserted. When calculateMKAverage is called, we sort the window and remove the smallest k and largest k elements to compute the average. Although sorting is an O(m log m) operation, this implementation is straightforward and intuitive.
The Python solution utilizes a deque to efficiently manage the sliding window. On adding a new element, we append it to the deque and pop elements from the left if the size exceeds m. For calculating the MKAverage, once we confirm the number of elements is sufficient, we sort the window, remove the smallest and largest k elements, and return the integer division of the sum of remaining elements by their count.
The time complexity for adding an element is O(1). The time complexity for calculating the MKAverage is O(m log m) due to sorting. The space complexity is O(m) as we store at most m elements.
This approach uses balanced binary search trees or any self-balancing data structure to efficiently manage the m elements along with retrieving/removing the smallest/largest k elements. While this complexity is higher for each insert, it provides a more efficient way to handle element removals and retrieval.
The Java solution uses a TreeMap to simulate a balanced binary search tree, allowing efficient insertion, deletion, and access to elements. While TreeMap in Java maintains a sorted order, additional logic is needed to ensure we handle groups of smallest and largest k elements. As elements are added beyond size m, the oldest elements are removed, and rebalance operations are performed.
Java
JavaScript
The time complexity for each operation (add or calculate) is O(log m) due to balanced tree operations. The space complexity is O(m) for storing the elements within the m-sized window.
We can maintain the following data structures or variables:
q of length m, where the head of the queue is the earliest added element, and the tail of the queue is the most recently added element;lo, mid, hi, where lo and hi store the smallest k elements and the largest k elements respectively, and mid stores the remaining elements;s, maintaining the sum of all elements in mid;size1 and size3, representing the number of elements in lo and hi respectively.When calling the addElement(num) function, perform the following operations in order:
lo is empty, or num leq max(lo), then add num to lo; otherwise if hi is empty, or num geq min(hi), then add num to hi; otherwise add num to mid, and add the value of num to s.num to the queue q. If the length of the queue q is greater than m at this time, remove the head element x from the queue q, then choose one of lo, mid or hi that contains x, and remove x from this set. If the set is mid, subtract the value of x from s.lo is greater than k, then repeatedly remove the maximum value max(lo) from lo, add max(lo) to mid, and add the value of max(lo) to s.hi is greater than k, then repeatedly remove the minimum value min(hi) from hi, add min(hi) to mid, and add the value of min(hi) to s.lo is less than k and mid is not empty, then repeatedly remove the minimum value min(mid) from mid, add min(mid) to lo, and subtract the value of min(mid) from s.hi is less than k and mid is not empty, then repeatedly remove the maximum value max(mid) from mid, add max(mid) to hi, and subtract the value of max(mid) from s.When calling the calculateMKAverage() function, if the length of q is less than m, return -1, otherwise return \frac{s}{m - 2k}.
In terms of time complexity, each call to the addElement(num) function has a time complexity of O(log m), and each call to the calculateMKAverage() function has a time complexity of O(1). The space complexity is O(m).
Python
| Approach | Complexity |
|---|---|
| Approach Using Sorting | The time complexity for adding an element is O(1). The time complexity for calculating the MKAverage is O(m log m) due to sorting. The space complexity is O(m) as we store at most m elements. |
| Approach Using Balanced Tree | The time complexity for each operation (add or calculate) is O(log m) due to balanced tree operations. The space complexity is O(m) for storing the elements within the m-sized window. |
| Ordered Set + Queue | — |
| Default Approach | — |
| 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 |
LeetCode 1825. Finding MK Average • Happy Coding • 4,863 views views
Watch 7 more video solutions →Practice Finding MK Average with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor