Finding MK Average - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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).

Q: 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.

Q: 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.

Q: 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.

HardDesign Queue Heap (Priority Queue)Data Stream20 min readAsked at: Google

Practice this problem

Problem Statement

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.

Approach Overview

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 1: Approach Using Sorting

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.

Code

Python C++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Approach Using Balanced Tree

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.

Code

Java JavaScript

Java

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Ordered Set + Queue

We can maintain the following data structures or variables:

A queue 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;
Three ordered sets, namely lo, mid, hi, where lo and hi store the smallest k elements and the largest k elements respectively, and mid stores the remaining elements;
A variable s, maintaining the sum of all elements in mid;
Some programming languages (such as Java, Go) additionally maintain two variables 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:

If 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.
Next, add 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.
If the length of 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.
If the length of 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.
If the length of 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.
If the length of 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).

Code

Python Java C++Go

Python

Java

C++

Try this approach in the editor →

Approach 4: Default Approach

Code

Python

Try this approach in the editor →

Complexity Comparison

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	—

Detailed Complexity Analysis

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

Video Solution

LeetCode 1825. Finding MK Average • Happy Coding • 4,944 views views

Watch 8 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Finding MK Average with our built-in code editor and test cases.

Practice on FleetCode

Find Median from Data Stream

Kth Largest Element in a Stream

Problem Info

DifficultyHard

Acceptance38.7%

Approaches4

Reading time20 min

Asked at

Google

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Approach Using Sorting

Code

Complexity

Approach 2: Approach Using Balanced Tree

Code

Complexity

Approach 3: Ordered Set + Queue

Code

Approach 4: Default Approach

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents