💬 Discord
Sign In
NeetCode #21LC-346EasyArrays & HashingNC Algo100
← Back to All Problems

#21 · #346 · Moving Average from Data Stream(数据流中的移动平均值)

📌 Problem Statement & Constraints

Design a class that computes the moving average of the last size values from a stream of integers, exposing a next(val) method that returns the new average. Constraints: 1 <= size <= 1000, -10^5 <= val <= 10^5; at most 10^4 calls.

💡 Core Algorithmic Approaches

  1. Keep a fixed-capacity FIFO queue of the most recent values, plus their running sum.
  2. On next(val): push val and add it to the sum.
  3. If the queue now exceeds size, pop the oldest value and subtract it from the sum.
  4. Return sum / len(queue). Maintaining the sum incrementally makes each call O(1) instead of O(size).

💻 Benchmark Python3 Implementation

class MovingAverage:
    def __init__(self, size: int):
        from collections import deque
        self.size = size
        self.q = deque()                   # only the most recent `size` values
        self.total = 0

    def next(self, val: int) -> float:
        self.q.append(val)
        self.total += val
        if len(self.q) > self.size:        # evict the oldest
            self.total -= self.q.popleft()
        return self.total / len(self.q)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1) per call. Recomputing sum(self.q) each time would be O(size) per call.
💾 Space Complexity
O(size) for the queue.

⚠️ Interview Pitfalls & Follow-ups

  • Recomputing the sum each call: O(size) per next, i.e. O(size * calls) overall.
  • Dividing by size instead of the current length: the first size - 1 calls have fewer than size values and must divide by the actual count.
  • Evicting after returning: the queue must be trimmed before computing the average, otherwise the window is one element too large.
  • Using integer division: the return type is float; Python's / is correct, // is not.