Is Finding MK Average easy or hard?

Finding MK Average is classified as a hard problem because it combines sliding window logic, ordered data structures, and dynamic rebalancing. Efficient solutions require careful handling of insertions, deletions, and maintaining the middle segment sum.

Finding MK Average Python/Java solution

Python implementations often simulate ordered sets using SortedList from the sortedcontainers library or multiple heaps with careful balancing. Java solutions commonly use TreeMap or TreeSet structures to maintain three partitions and track the running sum of the middle elements.

How to solve Finding MK Average in O(n)?

The problem is typically solved with O(log m) updates rather than strict O(n) overall complexity because each stream insertion requires rebalancing ordered sets. Maintaining three partitions and a running sum avoids re-sorting the entire window, which reduces repeated O(m log m) work.

What is the best approach for Finding MK Average?

The most efficient approach uses balanced trees (or multisets) to divide the window into three groups: the smallest k elements, the largest k elements, and the middle m−2k elements. The middle group maintains a running sum so the MKAverage can be returned instantly. Insertions and removals take O(log m) time while the query runs in O(1).

Is Finding MK Average asked at Google/Amazon/Meta?

Problems involving sliding windows, streaming statistics, and ordered data structures frequently appear in interviews at companies like Google, Amazon, and Meta. Finding MK Average tests system design thinking combined with balanced tree or heap-based data structures.

What data structure is used in Finding MK Average?

The optimal implementation relies on ordered sets or balanced binary search trees such as TreeMap, multiset, or similar structures. These maintain sorted order while supporting O(log m) insertions and deletions. A queue is also used to track the sliding window of the last m elements.

What is the time complexity of Finding MK Average?

The optimal solution runs in O(log m) time for each stream insertion because balanced tree operations handle ordered insertion and deletion. The MKAverage calculation itself is O(1) by maintaining the sum of the middle partition. Space complexity is O(m) to store the sliding window.

Description Hints 2 Solution Video 24:44

1825. Finding MK Average

Hard38.7% acceptance1 company

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:

If the number of the elements in the stream is less than m you should consider the MKAverage to be -1. Otherwise, copy the last m elements of the stream to a separate container.
Remove the smallest k elements and the largest k elements from the container.
Calculate the average value for the rest of the elements rounded down to the nearest integer.

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 <= 10⁵
1 <= k*2 < m
1 <= num <= 10⁵
At most 10⁵ calls will be made to addElement and calculateMKAverage.

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

At each query, try to save and update the sum of the elements needed to calculate MKAverage.

Hint 2

You can use BSTs for fast insertion and deletion of the elements.

24:44

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution