LeetCode 346: Moving Average from Data Stream - Comprehensive Solutions Guide

Problem Statement

Design a data structure that calculates the moving average of a stream of numbers with a fixed window size.

Copy codeInput:
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output:
[null, 1.0, 5.5, 4.66667, 6.0]

Explanation:
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3

Explanation

This approach: 1. Uses a circular queue to store values in the window 2. Maintains a running sum of current window elements 3. When window is full, replaces oldest element with new value 4. Adjusts sum accordingly and calculates average

Step-by-Step Example

For window size 3: 1. next(1): [1], sum=1, count=1 → avg=1.0 2. next(10): [1,10], sum=11, count=2 → avg=5.5 3. next(3): [1,10,3], sum=14, count=3 → avg=4.66667 4. next(5): [10,3,5], sum=18, count=3 → avg=6.0

Python Implementation

Copy codeclass MovingAverage:
    def __init__(self, size: int):
        self.size = size
        self.queue = [0] * size
        self.head = 0
        self.window_sum = 0
        self.count = 0  # Number of elements seen so far

    def next(self, val: int) -> float:
        self.count += 1
        # Calculate the tail position (where we'll overwrite)
        tail = (self.head + 1) % self.size
        # Subtract the element being overwritten
        self.window_sum = self.window_sum - self.queue[tail] + val
        # Move head forward and store new value
        self.head = tail
        self.queue[self.head] = val
        return self.window_sum / min(self.size, self.count)

Complexity Analysis

• Time Complexity: O(1) for each next call
• Space Complexity: O(size) for the circular buffer
• Why Optimal: Constant time operations with efficient space usage

Solution 2: Deque with Running Sum (Alternative)

Explanation

This alternative uses a deque: 1. Appends new values to the end 2. Pops from front when window is full 3. Maintains running sum of window elements

Python Implementation

Copy codefrom collections import deque

class MovingAverage:
    def __init__(self, size: int):
        self.size = size
        self.queue = deque()
        self.window_sum = 0

    def next(self, val: int) -> float:
        self.queue.append(val)
        self.window_sum += val
        if len(self.queue) > self.size:
            self.window_sum -= self.queue.popleft()
        return self.window_sum / len(self.queue)

Complexity Analysis

• Time Complexity: O(1) average case (O(n) worst case for deque growth)
• Space Complexity: O(size) for the deque
• Pros: Simpler implementation
• Cons: Slightly less predictable performance

Edge Cases to Consider

1. Window size 1: Should return each value
2. Single call: Return the single value
3. Values equal to zero: Should handle correctly
4. Maximum window size: Verify performance
5. Alternating large/small numbers: Check average calculations

Performance Comparison

Final Recommendations

• Circular queue solution is optimal for strict O(1) operations
• Deque solution is simpler to implement
• Understand running sum pattern for sliding window problems
• Problem teaches fundamental data stream processing