#1825

Hard

auto_awesomeQueue-driven state processing

LeetCode Problem Workspace

Finding MK Average

Find the MKAverage of a stream of integers using a queue-driven approach with efficient state management.

design queue heap priority queue data stream ordered set

Problem Statement

You are given two integers, m and k, and a stream of integers. Implement the MKAverage class to efficiently compute the MKAverage of the stream. The MKAverage for the current window is calculated by removing the smallest and largest k elements from the last m elements in the stream, and then computing the average of the remaining elements.

You need to handle multiple queries of adding an element to the stream and calculating the MKAverage. The stream can have up to 105 elements, and the class must efficiently manage and calculate averages for large inputs.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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

Solution Approach

Queue-Driven State Processing

The MKAverage class maintains a queue of the last m elements. On each query, when an element is added, it updates the queue, ensuring that only the relevant elements (the last m added) are kept. This sliding window approach helps efficiently track the necessary elements for average calculation.

Efficient Average Calculation

Instead of recalculating the average from scratch every time, maintain a running sum of the elements in the current window. By removing the smallest and largest k elements before averaging, the sum can be updated dynamically for efficiency.

Priority Queue or Sorted Data Structure

To efficiently remove the smallest and largest k elements, consider using a priority queue (heap) or a balanced tree. This allows fast retrieval and removal of the extreme values from the current window, optimizing the MKAverage calculation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of each operation depends on the approach used to manage the queue and calculate the MKAverage. If using a simple queue, inserting an element is O(1), but sorting the queue or removing elements could take longer. Using a priority queue or sorted data structure could optimize these operations to O(log m). The space complexity is O(m) as we maintain the last m elements in the stream.

What Interviewers Usually Probe

Look for the candidate's understanding of sliding window techniques.
Gauge their ability to optimize the insertion and average calculation process.
Check if the candidate considers edge cases where m is small or the stream has fewer than m elements.

Common Pitfalls or Variants

Common pitfalls

Not handling cases where the number of elements in the stream is less than m before the first MKAverage query.
Inefficient recalculation of the average by re-sorting or scanning all m elements.
Overcomplicating the solution by using unnecessary data structures, resulting in unnecessary time or space complexity.

Follow-up variants

Implement the solution using a deque to avoid sorting and ensure faster operations for average calculation.
Modify the problem to handle updates to the stream where elements can be removed or modified.
Extend the problem to calculate the MKAverage over different window sizes dynamically.

FAQ

What is the MKAverage problem about?

The MKAverage problem requires calculating an average from a stream of integers, where the smallest and largest k elements in the last m elements are removed before computing the average.

What is a queue-driven approach in this context?

A queue-driven approach involves maintaining a fixed-size queue of the last m elements from the stream, allowing efficient addition of new elements and calculation of the MKAverage.

How do you optimize the calculation of MKAverage?

You optimize the MKAverage calculation by maintaining a running sum of the elements and using efficient data structures like a priority queue to remove the smallest and largest elements.

What are some potential issues in solving the MKAverage problem?

Potential issues include inefficient recalculation of the average or using suboptimal data structures, leading to performance bottlenecks, especially with large streams.

How can GhostInterview help with the MKAverage problem?

GhostInterview provides a structured approach, offering insights into the most efficient data structures and methods for solving the MKAverage problem, reducing the likelihood of common pitfalls.

terminal

Solution

Solution 1: Ordered Set + Queue

We can maintain the following data structures or variables:

class MKAverage:
    def __init__(self, m: int, k: int):
        self.m = m
        self.k = k
        self.s = 0
        self.q = deque()
        self.lo = SortedList()
        self.mid = SortedList()
        self.hi = SortedList()

    def addElement(self, num: int) -> None:
        if not self.lo or num <= self.lo[-1]:
            self.lo.add(num)
        elif not self.hi or num >= self.hi[0]:
            self.hi.add(num)
        else:
            self.mid.add(num)
            self.s += num
        self.q.append(num)
        if len(self.q) > self.m:
            x = self.q.popleft()
            if x in self.lo:
                self.lo.remove(x)
            elif x in self.hi:
                self.hi.remove(x)
            else:
                self.mid.remove(x)
                self.s -= x
        while len(self.lo) > self.k:
            x = self.lo.pop()
            self.mid.add(x)
            self.s += x
        while len(self.hi) > self.k:
            x = self.hi.pop(0)
            self.mid.add(x)
            self.s += x
        while len(self.lo) < self.k and self.mid:
            x = self.mid.pop(0)
            self.lo.add(x)
            self.s -= x
        while len(self.hi) < self.k and self.mid:
            x = self.mid.pop()
            self.hi.add(x)
            self.s -= x

    def calculateMKAverage(self) -> int:
        return -1 if len(self.q) < self.m else self.s // (self.m - 2 * self.k)


# Your MKAverage object will be instantiated and called as such:
# obj = MKAverage(m, k)
# obj.addElement(num)
# param_2 = obj.calculateMKAverage()

Solution 2

#### Python3

class MKAverage:
    def __init__(self, m: int, k: int):
        self.m = m
        self.k = k
        self.s = 0
        self.q = deque()
        self.lo = SortedList()
        self.mid = SortedList()
        self.hi = SortedList()

    def addElement(self, num: int) -> None:
        if not self.lo or num <= self.lo[-1]:
            self.lo.add(num)
        elif not self.hi or num >= self.hi[0]:
            self.hi.add(num)
        else:
            self.mid.add(num)
            self.s += num
        self.q.append(num)
        if len(self.q) > self.m:
            x = self.q.popleft()
            if x in self.lo:
                self.lo.remove(x)
            elif x in self.hi:
                self.hi.remove(x)
            else:
                self.mid.remove(x)
                self.s -= x
        while len(self.lo) > self.k:
            x = self.lo.pop()
            self.mid.add(x)
            self.s += x
        while len(self.hi) > self.k:
            x = self.hi.pop(0)
            self.mid.add(x)
            self.s += x
        while len(self.lo) < self.k and self.mid:
            x = self.mid.pop(0)
            self.lo.add(x)
            self.s -= x
        while len(self.hi) < self.k and self.mid:
            x = self.mid.pop()
            self.hi.add(x)
            self.s -= x

    def calculateMKAverage(self) -> int:
        return -1 if len(self.q) < self.m else self.s // (self.m - 2 * self.k)


# Your MKAverage object will be instantiated and called as such:
# obj = MKAverage(m, k)
# obj.addElement(num)
# param_2 = obj.calculateMKAverage()

Continue Practicing

#2034 stock price fluctuation #2102 sequentially ordinal rank tracker #1912 design movie rental system