Sliding Window Average After Dropping the Largest Values

Problem Statement

Given an array of integers nums, a window size w, and an integer k, compute the average of the elements in each sliding window of size w after removing the k largest values.

If the window contains duplicates, treat each occurrence as a distinct value to be removed. If k is 0, return the average of all elements in the window. The result for each window should be the sum of the remaining w - k elements divided by (w - k).

Function Signature

def sliding_window_average(nums: List[int], w: int, k: int) -> List[float]:

Constraints

• 1 <= w <= len(nums) <= 200,000
• 0 <= k < w
• -10^6 <= nums[i] <= 10^6

Example

Input: nums = [1, 5, 2, 8, 3], w = 3, k = 1

1. Window [1, 5, 2]: Largest is 5. Remaining: [1, 2]. Average: 1.5
2. Window [5, 2, 8]: Largest is 8. Remaining: [5, 2]. Average: 3.5
3. Window [2, 8, 3]: Largest is 8. Remaining: [2, 3]. Average: 2.5 Output: [1.5, 3.5, 2.5]

Edge Cases

• k = 0 (Simple sliding window sum)
• k = w - 1 (Only the smallest element remains)
• All elements in the window are identical.