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.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.
C++
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.
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.
| 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. |
I HATE This Coding Question, but FAANG Loves it! | Majority Element - Leetcode 169 • Greg Hogg • 2,093,916 views views
Watch 9 more video solutions →Practice Finding MK Average with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor