Practice/Meta/Leetcode 2854. Rolling Average Steps

Leetcode 2854. Rolling Average Steps

CodingMust

Problem

You are given an array of numerical values and a window size. Your task is to compute the moving average (also called sliding window average) for each contiguous subsequence of the specified window size.

For an array of length n and window size k, you should return an array of length n - k + 1, where each element represents the average of a window of k consecutive elements from the original array.

The key challenge is efficiency: your solution should process each new value in constant time O(1) rather than recalculating the entire sum for each window.

Requirements

1. Return an array of floating-point averages for each complete window
2. Handle edge cases where the window size equals or exceeds the array length
3. Support negative numbers in the input array
4. Achieve O(1) time complexity for processing each new window (O(n) overall)
5. Round results to 2 decimal places for comparison purposes

Constraints

• 1 <= values.length <= 100,000
• 1 <= window_size <= values.length
• -10,000 <= values[i] <= 10,000
• Expected time complexity: O(n) where n is the length of the values array
• Expected space complexity: O(n - k + 1) for the output array

Examples

Example 1:

Input: values = [1, 3, 2, 6, -1, 4, 1, 8, 2], window_size = 3 Output: [2.0, 3.67, 2.33, 3.0, 1.33, 4.33, 3.67] Explanation: Window [1, 3, 2] → average = 6/3 = 2.0 Window [3, 2, 6] → average = 11/3 = 3.67 Window [2, 6, -1] → average = 7/3 = 2.33 And so on...

Example 2:

Input: values = [5, 10, 15, 20], window_size = 4 Output: [12.5] Explanation: Only one complete window exists: [5, 10, 15, 20] with average 50/4 = 12.5

Example 3:

Input: values = [7, 2, 9, 4], window_size = 1 Output: [7.0, 2.0, 9.0, 4.0] Explanation: Each single element forms its own window