Practice Finding MK Average

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Hard#1825

LeetCode Problem

Finding MK Average

Design Queue Heap (Priority Queue)Data Stream Ordered Set

Problem Statement

MKAverage(m,k) accepts addElement(num) calls. calculateMKAverage() returns -1 until at least m values exist. Otherwise consider only the latest m, remove exactly k smallest and k largest occurrences, and return the floor of the remaining arithmetic mean. Duplicates count separately. Practice approach: Keep a FIFO window and three balanced multisets for low, middle, and high values, maintaining the middle sum. Rebalance after both insertion and expiration. A Fenwick tree over the bounded value domain can also maintain counts and sums by rank. Test duplicate boundary values and expiration from each group.

Source: Finding MK Average on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input

["MKAverage","addElement","addElement","calculateMKAverage","addElement","addElement","addElement","calculateMKAverage","addElement","calculateMKAverage"]
[[5,1],[1],[4],[],[7],[9],[10],[],[6],[]]

Output

[null,null,null,-1,null,null,null,6,null,7]

Explanation

The first full window trims 1 and 10, averaging [4,7,9] to floor 6. The next window trims 4 and 10, averaging [6,7,9] to floor 7.

Constraints

3 <= m <= 10^5

1 < 2*k < m

1 <= num <= 10^5

At most 10^5 total calls.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.

Start Free