Leetcode 2854. Rolling Average Steps

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?

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 cases
    if not step_counts or window_size <= 0:
        return []
    
    # Store results
    averages = []
    n = len(step_counts)
    
    # Iterate through each possible window position
    for i in range(n - window_size + 1):
        # Recalculate sum for current window from scratch
        window_sum = 0
        
        # Sum all elements in current window
        for j in range(i, i + window_size):
            window_sum += step_counts[j]
        
        # Calculate average for this window
        average = window_sum / window_size
        averages.append(average)
    
    return averages

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.

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 window
    window_sum = 0
    for i in range(k):
        window_sum += step_counts[i]
    
    # First window average
    averages.append(window_sum / k)
    
    # Slide window: remove left, add right
    for i in range(k, n):
        window_sum = window_sum - step_counts[i - k] + step_counts[i]
        averages.append(window_sum / k)
    
    return averages

• 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.