We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Finding MK Average

Difficulty: Hard

Problem Description

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 specific steps involving the last m elements of the stream.

Key Insights

  • If the number of elements in the stream is less than m, the MKAverage should return -1.
  • The MKAverage is calculated by removing the smallest k and largest k elements from the last m elements of the stream.
  • The average of the remaining elements is returned, rounded down to the nearest integer.
  • Efficiently managing the stream and performing operations on a dynamic size of data requires the use of appropriate data structures.

Space and Time Complexity

Time Complexity: O(n log m) for maintaining the data structure, where n is the number of elements added. Space Complexity: O(m) for storing the last m elements of the stream.

Solution

To solve the problem, we can utilize a combination of a list to maintain the stream of elements and a sorted data structure (such as a balanced binary search tree or two heaps) to efficiently handle the removal of the smallest and largest k elements. The steps are as follows:

  1. Maintain a list to store the elements added to the stream.
  2. When calculating the MKAverage, if the number of elements is less than m, return -1.
  3. Extract the last m elements and sort them.
  4. Remove the smallest k and largest k elements.
  5. Calculate the average of the remaining elements and round it down.

This approach allows us to efficiently retrieve the last m elements and calculate the MKAverage.

Code Solutions

class MKAverage:

    def __init__(self, m: int, k: int):
        self.m = m  # The size of the window to consider
        self.k = k  # The number of smallest and largest elements to remove
        self.stream = []  # List to store the stream of elements

    def addElement(self, num: int) -> None:
        self.stream.append(num)  # Add the new element to the stream

    def calculateMKAverage(self) -> int:
        if len(self.stream) < self.m:
            return -1  # Not enough elements to calculate MKAverage

        # Get the last m elements
        last_m_elements = self.stream[-self.m:]
        last_m_elements.sort()  # Sort the elements

        # Remove the smallest k and largest k elements
        relevant_elements = last_m_elements[self.k:self.m - self.k]

        # Calculate the average of the remaining elements
        if not relevant_elements:
            return 0  # If no elements left, the average is 0

        return sum(relevant_elements) // len(relevant_elements)  # Return the average rounded down
← Back to All Questions