Skip to content
Codeloom
DSA

Moving Average from Data Stream Using Queue

Calculate the moving average from a data stream using a queue with fixed window size. LeetCode 346 solution with O(1) per operation.

·2 min read · By Codeloom
Beginner 10 min read

What you'll learn

  • ✓How to maintain a running average with a fixed window
  • ✓Queue as a sliding window data structure
  • ✓O(1) time per operation using a running sum
  • ✓Real-world applications in signal processing

Prerequisites

Moving average with queue-based sliding window

Design a class that calculates the moving average of the last size values from a data stream.

Solution

from collections import deque

class MovingAverage:
    def __init__(self, size):
        self.size = size
        self.queue = deque()
        self.total = 0
    
    def next(self, val):
        """
        Add value and return current moving average.
        Time: O(1), Space: O(size)
        """
        self.queue.append(val)
        self.total += val

        if len(self.queue) > self.size:
            self.total -= self.queue.popleft()

        return self.total / len(self.queue)

Trace

MovingAverage(size=3)

next(1):  queue=[1],       total=1,  avg=1/1 = 1.0
next(10): queue=[1,10],    total=11, avg=11/2 = 5.5
next(3):  queue=[1,10,3],  total=14, avg=14/3 = 4.667
next(5):  queue=[10,3,5],  total=18, avg=18/3 = 6.0   ← 1 removed

Why Not Recalculate?

Summing all elements each time is O(size). By maintaining a running sum and subtracting the removed element, each operation is O(1).

Circular Buffer Alternative

class MovingAverageCircular:
    def __init__(self, size):
        self.size = size
        self.buffer = [0] * size
        self.total = 0
        self.count = 0
        self.idx = 0
    
    def next(self, val):
        self.total -= self.buffer[self.idx]
        self.buffer[self.idx] = val
        self.total += val
        self.idx = (self.idx + 1) % self.size
        self.count = min(self.count + 1, self.size)
        return self.total / self.count

Edge Cases

  • Window not full yet — divide by actual count, not size
  • Single element window — each value is its own average
  • Negative values — works correctly with running sum
  • Very large values — consider overflow in languages without arbitrary precision

When to Use This Pattern

  • Financial data (moving average of stock prices)
  • Sensor smoothing (noise reduction)
  • Network monitoring (average latency over window)
  • Any streaming aggregation with fixed window
  • Design Hit Counter (LeetCode 362)
  • Number of Recent Calls (LeetCode 933)
  • Sliding Window Median (LeetCode 480)

Related articles