How do you solve Finding MK Average on LeetCode?

Finding MK Average (LeetCode #1825) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log m) time complexity and O(m) space complexity. Key insight: Maintaining a sorted structure allows for efficient access to the smallest and largest elements.

What is the brute force solution for Finding MK Average?

The brute force approach for Finding MK Average is Brute Force, with O(n²) time complexity and O(m) space complexity. The brute-force approach involves maintaining a simple list of the last 'm' elements and calculating the MKAverage by sorting this list to remove the smallest and largest 'k' elements. This method is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n log m).

What algorithm or data structure is used to solve Finding MK Average?

Finding MK Average uses the following concepts: Design, Queue, Heap (Priority Queue), Data Stream, Ordered Set. The recommended patterns to study are: Hash Map, Array, Sliding Window.

What are the interview tips for Finding MK Average?

Explain your thought process clearly while coding. Discuss the trade-offs of different data structures you consider. Test your code with edge cases, like adding elements that are all the same.

What are common mistakes when solving Finding MK Average?

Forgetting to handle the case when the stream has less than 'm' elements. Not updating the sorted structure correctly when elements are added or removed.

#1825

Finding MK Average

Hard

DesignQueueHeap (Priority Queue)Data StreamOrdered SetHash MapArraySliding Window

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log m)
Space	O(m)	O(m)

💡

Intuition

Time O(n log m)Space O(m)

The optimal approach uses a combination of a deque and a balanced binary search tree (or a sorted list) to efficiently maintain the last 'm' elements and quickly compute the MKAverage without needing to sort every time.

⚙️

Algorithm

3 steps

1Step 1: Use a deque to store the last 'm' elements of the stream.
2Step 2: Maintain a sorted data structure (like a SortedList or a balanced BST) to keep track of the elements for quick access to the smallest and largest 'k' elements.
3Step 3: When calculating MKAverage, directly access the smallest and largest 'k' elements from the sorted structure and compute the average of the remaining elements.

solution.py22 lines

1from collections import deque
2import sortedcontainers
3
4class MKAverage:
5    def __init__(self, m: int, k: int):
6        self.m = m
7        self.k = k
8        self.stream = deque()
9        self.sorted_elements = sortedcontainers.SortedList()
10
11    def addElement(self, num: int) -> None:
12        self.stream.append(num)
13        self.sorted_elements.add(num)
14        if len(self.stream) > self.m:
15            removed = self.stream.popleft()
16            self.sorted_elements.remove(removed)
17
18    def calculateMKAverage(self) -> int:
19        if len(self.stream) < self.m:
20            return -1
21        relevant_elements = self.sorted_elements[self.k:self.m - self.k]
22        return sum(relevant_elements) // len(relevant_elements)

ℹ

Complexity note: The time complexity is O(n log m) because each insertion and deletion in the sorted structure takes logarithmic time, and we do this for each element in the stream. The space complexity is O(m) due to storing the last 'm' elements.

1Maintaining a sorted structure allows for efficient access to the smallest and largest elements.
2Using a deque helps manage the stream of elements efficiently.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.