Practice/Google/Leetcode 1825. Finding MK Average

Leetcode 1825. Finding MK Average

CodingMust

Problem

Design a data structure that processes a continuous stream of integers and supports two operations:

1. addElement(num): Add a new integer to the stream
2. calculateMKAverage(): Calculate the average of the middle elements after removing outliers

The data structure maintains a sliding window of the most recent m elements. When calculating the average, you must:

• Discard the k smallest values
• Discard the k largest values
• Return the integer division average of the remaining elements
• Return -1 if fewer than m elements have been added to the stream

The key challenge is maintaining efficient access to sorted statistics over a moving window as new elements arrive and old elements are evicted.

Requirements

1. Implement a class constructor that accepts parameters m and k
2. The addElement method should process incoming stream values efficiently
3. The calculateMKAverage method should return the truncated average after removing k smallest and k largest values
4. Handle the case where fewer than m elements exist (return -1)
5. Maintain correctness as the sliding window moves through the stream

Constraints

• 3 ≤ m ≤ 105
• 1 ≤ k × 2 < m (ensures at least one element remains after removing outliers)
• 1 ≤ num ≤ 105
• At most 105 calls will be made to addElement and calculateMKAverage combined
• Target time complexity: O(log m) per operation

Examples

Example 1:

` Operations: MKAverage obj = new MKAverage(3, 1) obj.addElement(3) obj.addElement(1) obj.addElement(10) obj.calculateMKAverage() // returns 3

Explanation: Window contains [3, 1, 10] After sorting: [1, 3, 10] Remove 1 smallest (1) and 1 largest (10) Remaining: [3] Average: 3 // 1 = 3 `

Example 2:

` Operations: MKAverage obj = new MKAverage(6, 2) obj.addElement(3) obj.addElement(1) obj.calculateMKAverage() // returns -1

Explanation: Only 2 elements added, but m=6 requires at least 6 elements `

Example 3:

` Operations: MKAverage obj = new MKAverage(6, 2) obj.addElement(3) obj.addElement(1) obj.addElement(10) obj.addElement(5) obj.addElement(5) obj.addElement(5) obj.calculateMKAverage() // returns 5 obj.addElement(8) obj.calculateMKAverage() // returns 5

Explanation: First query: Window [3,1,10,5,5,5], sorted [1,3,5,5,5,10] Remove 2 smallest (1,3) and 2 largest (5,10): middle [5,5] Average: 10 // 2 = 5

Second query: Window [1,10,5,5,5,8], sorted [1,5,5,5,8,10]
Remove 2 smallest (1,5) and 2 largest (8,10): middle [5,5] Average: 10 // 2 = 5 `