Sliding Window Average Excluding the Largest K Values

Given an integer array values, an integer windowSize, and a non-negative integer k, compute one average for every contiguous window of length windowSize.
Within each window, ignore the k elements with the largest values, counting equal values as separate elements. Average the remaining windowSize - k elements, and return the averages in left-to-right window order.
The inputs are guaranteed to satisfy 0 <= k < windowSize <= values.length. When k = 0, ignore no elements and average the entire window.
Follow-up
How would the approach change if the input were very large or arrived as a stream?

Function
slidingWindowAverageExcludingLargestK(values: int[], windowSize: int, k: int) → double[]

Examples
Example 1
values = [1,3,2,6,4]
windowSize = 3
k = 1
return = [1.5,2.5,3.0]
The windows are [1,3,2], [3,2,6], and [2,6,4]. Removing the largest value from each leaves [1,2], [3,2], and [2,4], whose averages are 1.5, 2.5, and 3.0.
Example 2
values = [2,-2,4]
windowSize = 2
k = 0
return = [0.0,1.0]
Because k = 0, both values remain in each window. The averages of [2,-2] and [-2,4] are 0.0 and 1.0.
Example 3
values = [5,5,1,2]
windowSize = 3
k = 2
return = [1.0,1.0]
In [5,5,1], both occurrences of 5 are ignored. In [5,1,2], 5 and 2 are ignored. The only retained value is 1 in both windows.

Brute force sorts each window: O(n * w log w). It's correct and usually too slow. The better approach keeps the window split into two multisets: the top k values and the rest. Track the sum of the rest. When the window slides, remove the outgoing value from whichever side holds it, insert the incoming value, then rebalance so the top set has exactly k elements. Two heaps with lazy deletion work, or a sorted structure with order statistics. The pitfall is duplicates. If you track by value instead of by index, removing one 5 can wipe out the wrong copy. Store (value, index) pairs or use counts. Also handle k = 0 as an empty top set, and use long for sums to avoid overflow. If the rebalancing logic gets tangled mid-assessment, StealthCoder is the hedge that hands you a clean version while you stay in control of the submission.

If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.