🧩 Problem Statement
Given a stream of integers and a window size, implement a class MovingAverage that calculates the moving average of all integers in the sliding window.
🔢 Example
python
Input:
MovingAverage m = new MovingAverage(3);
m.next(1); // return 1.0
m.next(10); // return 5.5
m.next(3); // return 4.66667
m.next(5); // return 6.0
✅ Constraints
1 <= window size <= 10⁴-10⁵ <= value <= 10⁵- Total calls to
next will not exceed 10⁴
💡 Key Concept: Sliding Window with a Queue
To solve this, we can:
- Maintain a queue to hold the last
size elements
- Keep track of the current sum of elements in the queue
- When adding a new number:
- Add it to the queue
- Add it to the sum
- If the queue size exceeds the window size, remove the oldest number from the queue and subtract it from the sum
- Return
sum / len(queue)
✅ Python Code – Using collections.deque
python
from collections import deque
class MovingAverage:
def __init__(self, size: int):
self.queue = deque()
self.size = size
self.window_sum = 0
def next(self, val: int) -> float:
self.queue.append(val)
self.window_sum += val
if len(self.queue) > self.size:
removed = self.queue.popleft()
self.window_sum -= removed
return self.window_sum / len(self.queue)
🔍 Step-by-Step Example (Window Size = 3)
python
Input stream: [1, 10, 3, 5]
Step 1: Add 1 → queue: [1], sum: 1 → average = 1 / 1 = 1.0
Step 2: Add 10 → queue: [1, 10], sum: 11 → average = 11 / 2 = 5.5
Step 3: Add 3 → queue: [1, 10, 3], sum: 14 → average = 14 / 3 ≈ 4.67
Step 4: Add 5 → queue: [10, 3, 5], removed 1, sum: 18 → average = 18 / 3 = 6.0
⏱️ Time and Space Complexity
MetricValueTime ComplexityO(1) per next() callSpace ComplexityO(size)
Efficient for streaming large amounts of data without reprocessing the entire array.
📦 Real-World Applications
- Sensor data smoothing (e.g., temperature, heart rate)
- Stock market analytics (e.g., moving average price)
- Monitoring systems (e.g., CPU usage over last 5 mins)
✅ Conclusion
LeetCode 346: Moving Average from Data Stream is a practical and elegant problem that introduces the sliding window concept. Using a queue (deque) and rolling sum, it handles real-time data efficiently.
It’s perfect for interviews focusing on streaming data, performance, and data structures like queues and deques.