Leetcode 2854. Rolling Average Steps
Compute the moving average of step counts over a fixed-size sliding window for an array or stream of measurements, producing the average for each contiguous window efficiently. The core challenge is to update the average incrementally (O(1) per new value) to handle large or streaming inputs and edge cases like partial windows.
Asked at:
Meta
DESCRIPTION
Compute the moving average of step counts over a fixed-size sliding window for an array or stream of measurements, producing the average for each contiguous window efficiently. The core challenge is to update the average incrementally (O(1) per new value) to handle large or streaming inputs and edge cases like partial windows.
Input:
nums = [100, 200, 300, 400, 500], k = 3
Output:
[200, 300, 400]
Explanation: Window 1: [100,200,300] avg=200. Window 2: [200,300,400] avg=300. Window 3: [300,400,500] avg=400
Constraints:
- 1 <= nums.length <= 10^5
- 1 <= k <= nums.length
- -10^4 <= nums[i] <= 10^4
- Must compute each average in O(1) time after initial window
Understanding the Problem
Let's understand what we're being asked to do. We have an array of step counts like [100, 200, 300, 400, 500] and a window size like k=3. We need to compute the average for each contiguous window of 3 elements.
Tracing through: The first window [100, 200, 300] has average (100+200+300)/3 = 200. The second window [200, 300, 400] has average (200+300+400)/3 = 300. The third window [300, 400, 500] has average (300+400+500)/3 = 400.
Important constraint: We need to compute this incrementally in O(1) time per new value, not recalculate the entire sum each time. This is crucial for handling large or streaming inputs efficiently.
Edge cases to consider: What if the array has fewer elements than the window size? (partial window). What if k=1? (each element is its own average). What about very large numbers that might cause overflow when summing?
Brute Force Approach
The straightforward approach is to iterate through each possible window position and calculate the sum of all k elements in that window from scratch. For each window starting at index i, sum elements from i to i+k-1, then divide by k to get the average. This approach is simple to understand but recalculates overlapping sums repeatedly, leading to inefficiency.
def moving_average_brute_force(step_counts, window_size):"""Compute moving average using brute force approach.For each window position, recalculate sum from scratch.Time: O(n*k) where n is array length, k is window size."""# Handle edge casesif not step_counts or window_size <= 0:return []# Store resultsaverages = []n = len(step_counts)# Iterate through each possible window positionfor i in range(n - window_size + 1):# Recalculate sum for current window from scratchwindow_sum = 0# Sum all elements in current windowfor j in range(i, i + window_size):window_sum += step_counts[j]# Calculate average for this windowaverage = window_sum / window_sizeaverages.append(average)return averages
Start moving average calculation
0 / 41
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n * k) For each of the n-k+1 windows, we sum k elements, resulting in O(n*k) total operations
Space Complexity: O(1) We only use a constant amount of extra space for the current sum and result array
Building Intuition
When we slide the window from [100, 200, 300] to [200, 300, 400], notice that we're removing 100 and adding 400. The middle elements [200, 300] stay in both windows!
This means we don't need to recalculate the entire sum - we can just subtract the element leaving and add the element entering.
By maintaining a running sum and updating it incrementally, we transform an O(k) operation (summing k elements) into an O(1) operation (one subtraction and one addition).
For a stream of 1,000,000 values with window size 1000, this is the difference between 1 trillion operations and just 2 million operations!
Imagine a physical sliding window over an array of blocks. As you slide it one position to the right:
- One block exits on the left side
- One block enters on the right side
- All blocks in between stay inside the window
Instead of counting all blocks inside the window each time, just subtract the exiting block's value and add the entering block's value to your running count. This 'incremental update' pattern is the essence of efficient sliding window algorithms.
Common Mistakes
Optimal Solution
The optimal approach maintains a running sum of the current window. Start by calculating the sum of the first k elements. Then, for each subsequent position, subtract the element that exits the window on the left and add the element that enters on the right. This incremental update allows us to compute each new average in constant time, achieving O(1) per element after the initial window setup.
def moving_average(step_counts, k):"""Compute moving average of step counts over a sliding window of size k.Returns list of averages for each valid window position."""if not step_counts or k <= 0:return []n = len(step_counts)if k > n:return []averages = []# Calculate sum of first windowwindow_sum = 0for i in range(k):window_sum += step_counts[i]# First window averageaverages.append(window_sum / k)# Slide window: remove left, add rightfor i in range(k, n):window_sum = window_sum - step_counts[i - k] + step_counts[i]averages.append(window_sum / k)return averages
start
Start moving average calculation
0 / 10
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n) We process each element exactly once: k elements for initial window, then n-k elements for sliding updates, totaling O(n)
Space Complexity: O(1) We only maintain a running sum variable and result array, using constant extra space beyond the output
What We've Learned
- Sliding window with running sum: Instead of recalculating the average from scratch for each window (O(n*k)), maintain a running sum and update it incrementally by adding the new element and subtracting the element that slides out - this reduces each update to O(1) and total complexity to O(n).
- Deque for window management: Use a deque (double-ended queue) to efficiently track window elements - it allows O(1) additions at the back and O(1) removals from the front, making it perfect for maintaining a fixed-size sliding window where elements enter and exit in FIFO order.
- Partial window handling: For the first k-1 elements, you have incomplete windows - decide whether to output averages for partial windows (dividing by current size) or wait until the full window is available; this design choice affects edge case behavior and should match requirements.
- Floating-point precision: Always use float or double division when computing averages (sum / window_size) to avoid integer truncation errors; in languages like Python use `/` not `//`, and be aware that accumulated floating-point errors can occur with very large streams.
- Stream processing pattern: This incremental update technique applies broadly to any aggregate statistic over sliding windows (sum, average, variance) - recognize that when you can express the new state as old_state - exiting_element + entering_element, you can avoid full recalculation.
- Real-time analytics application: This pattern powers real-time monitoring dashboards (CPU usage over last 5 minutes, rolling stock prices, sensor data smoothing) where you need continuously updated statistics without storing or reprocessing the entire history - critical for IoT, financial systems, and health monitoring devices.
Related Concepts and Problems to Practice
easy
This problem uses the same fixed-size sliding window pattern as rolling averages. Instead of computing averages, it computes sums, but the core technique of maintaining a running sum and updating it incrementally in O(1) time is identical to the rolling average problem.
medium
This problem extends the fixed-size sliding window pattern by adding constraints while maintaining the same O(1) incremental update approach. It reinforces efficient window management techniques that are essential for handling streaming data in rolling average calculations.
Test Your Understanding
Why is sliding-window the right data structure for this problem?
sliding-window provides the optimal access pattern
It's the only data structure that works
It's the easiest to implement
It uses the least memory
Select an answer to see the explanation
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late November, 2025
Meta
Staff
Late August, 2024
Meta
Senior
Given an array of integers and a window size, write a function that returns the average value for each rolling window.
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.