Finding MK Average - Practice Coding Problems

Finding MK Average - Problem

You are given two integers, m and k, and a stream of integers. You need to implement a data structure that calculates the MKAverage for the stream.

The MKAverage can be calculated using these steps:

If the number of elements in the stream is less than m, the MKAverage is -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 remaining 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.

Input & Output

Example 1 — Basic Operations

$ Input: MKAverage(3, 1), addElement(3), addElement(1), addElement(10), addElement(5), addElement(5), addElement(5), calculateMKAverage()

› Output: [null, null, null, null, null, null, null, 5]

💡 Note: After adding [3,1,10,5,5,5], last 3 elements are [5,5,5]. Remove 1 smallest and 1 largest: middle element is 5, so average is 5.

Example 2 — Insufficient Elements

$ Input: MKAverage(3, 1), addElement(3), addElement(1), calculateMKAverage()

› Output: [null, null, null, -1]

💡 Note: Only 2 elements in stream, but need m=3 elements minimum, so return -1.

Example 3 — Different Values

$ Input: MKAverage(5, 2), addElement(3), addElement(1), addElement(12), addElement(5), addElement(3), addElement(4), calculateMKAverage()

› Output: [null, null, null, null, null, null, null, 4]

💡 Note: Last 5 elements: [1,12,5,3,4]. Sorted: [1,3,4,5,12]. Remove 2 smallest [1,3] and 2 largest [5,12]. Middle: [4]. Average = 4.

Constraints

1 ≤ m ≤ 10⁵
1 ≤ k*2 < m
1 ≤ num ≤ 10⁵
At most 10⁵ calls to addElement and calculateMKAverage

Visualization

Tap to expand

Understanding the Visualization

Stream Input

Elements arrive: 3, 1, 10, 5, 5, 5

Last m=3

Take last 3 elements: [5, 5, 5]

Remove Extremes

Remove k=1 smallest and largest: middle = [5]

Calculate Average

Average of middle elements = 5

Key Takeaway

🎯 Key Insight: Use balanced data structures to efficiently maintain sorted sliding window for fast extreme removal and average calculation

Asked in

a Amazon 15 G Google 12 M Microsoft 8 Apple 6

The key insight is to maintain a sliding window of the last m elements while keeping them sorted for efficient range queries. The optimal approach uses balanced data structures like TreeMap or multiset to achieve O(log m) time complexity per operation. Time: O(log m), Space: O(m).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Sort Every Time	O(m log m)	O(n)	Store all elements, sort the last m elements for each query
Optimized with Balanced Data Structures	O(log m)	O(m)	Use multiset and deque to efficiently maintain sorted order

Brute Force - Sort Every Time — Algorithm Steps

Store each new element in a list
When calculating average, get last m elements
Sort these m elements
Remove k smallest and k largest
Calculate average of remaining elements

Visualization

Tap to expand

Step-by-Step Walkthrough

Store Elements

Add elements to stream array

Extract Last m

Get the most recent m elements

Sort and Filter

Sort and remove k smallest and k largest

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int m, k;
    int* stream;
    int size;
    int capacity;
} MKAverage;

MKAverage* mkAverageCreate(int m, int k) {
    MKAverage* obj = (MKAverage*)malloc(sizeof(MKAverage));
    obj->m = m;
    obj->k = k;
    obj->stream = (int*)malloc(100000 * sizeof(int));
    obj->size = 0;
    obj->capacity = 100000;
    return obj;
}

void mkAverageAddElement(MKAverage* obj, int num) {
    obj->stream[obj->size++] = num;
}

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int mkAverageCalculateMKAverage(MKAverage* obj) {
    if (obj->size < obj->m) {
        return -1;
    }
    
    int lastM[obj->m];
    for (int i = 0; i < obj->m; i++) {
        lastM[i] = obj->stream[obj->size - obj->m + i];
    }
    
    qsort(lastM, obj->m, sizeof(int), compare);
    
    long long sum = 0;
    for (int i = obj->k; i < obj->m - obj->k; i++) {
        sum += lastM[i];
    }
    
    return sum / (obj->m - 2 * obj->k);
}

int main() {
    printf("[null,null,null,null,null,5]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m log m)

Each calculateMKAverage call requires sorting m elements

⚡ Linearithmic

Space Complexity

O(n)

Store all n elements in the stream

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~45 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Sort Every Time — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler