Log inSign up
easyLeetCodeNot Started

Moving Average from Data Stream

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Queue
Solve on LeetCode
Lesson

Problem Statement

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Implement the MovingAverage class: - MovingAverage(int size) Initializes the object with the size of the window size. - double next(int val) Returns the moving average of the last size values of the stream.

Example 1 · Window Size 3 Stream:

Input: ["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 (1 falls out of window)

Constraints:

  • 1 <= size <= 1000
  • -105 <= val <= 105
  • At most 104 calls will be made to next.

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Queue FIFO Basics
  • Running Sum Maintenance

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Apply sliding window techniques to streaming time-series data.
  • Maintain cumulative state variables to achieve O(1) query time.
  • Understand rolling metrics in production telemetry, finance, and monitoring.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Continuous stream with fixed-length trailing window calculation.
  • Running statistics (average, variance, sum) over time.

Algorithmic Decision Tree:

  • Use a FIFO Queue to track window elements.
  • Evict oldest item when queue size exceeds window size.

Connected Patterns:

Number of Recent CallsDesign Circular QueueSliding Window Maximum

1. Brute Force — Recalculate Sum on Every Call

Intuition

Append each value to a list. Sum the last min(N, size) items on every tick.

Algorithm

  1. Step 1: Append value to history list.
  2. Step 2: Take slice of the last min(len, size) elements.
  3. Step 3: Sum the slice and divide by slice length.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4
5using namespace std;
6
7class MovingAverage {
8private:
9 vector<int> stream;
10 int windowSize;
11public:
12 MovingAverage(int size) : windowSize(size) {}
13
14 double next(int val) {
15 stream.push_back(val);
16 int count = min((int)stream.size(), windowSize);
17 double sum = 0;
18 for (int i = stream.size() - count; i < stream.size(); ++i) {
19 sum += stream[i];
20 }
21 return sum / count;
22 }
23};
24
25int main() {
26 MovingAverage ma(3);
27 cout << ma.next(1) << endl; // 1.0
28 cout << ma.next(10) << endl; // 5.5
29 cout << ma.next(3) << endl; // 4.66667
30 cout << ma.next(5) << endl; // 6.0
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(W) per call — Iterates through the last W elements on every call.
  • Space complexity: O(N) total history — Stores all incoming stream values.

Why Brute Force Doesn't Scale:

For high-throughput telemetry (100,000 events/sec), O(W) causes latency buildup.

Running sum with queue takes 20 nanoseconds per event.

2. Better — Circular Array Buffer

Intuition

Use a circular array. Overwrite element at head index, adjusting running sum.

Algorithm

  1. Step 1: Track head = 0, count = 0, and windowSum = 0.
  2. Step 2: count++. tail = (head + 1) % size.
  3. Step 3: windowSum = windowSum - buffer[head] + val.
  4. Step 4: buffer[head] = val; head = tail.
  5. Step 5: Return windowSum / min(count, size).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class MovingAverage {
7private:
8 vector<int> buffer;
9 int size;
10 int head;
11 int count;
12 double windowSum;
13public:
14 MovingAverage(int k) : size(k), head(0), count(0), windowSum(0.0), buffer(k, 0) {}
15
16 double next(int val) {
17 count++;
18 windowSum = windowSum - buffer[head] + val;
19 buffer[head] = val;
20 head = (head + 1) % size;
21 return windowSum / min(count, size);
22 }
23};
24
25int main() {
26 MovingAverage ma(3);
27 cout << ma.next(1) << endl;
28 cout << ma.next(10) << endl;
29 cout << ma.next(3) << endl;
30 cout << ma.next(5) << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(1) per call — Direct index write with subtraction and addition in O(1).
  • Space complexity: O(W) Fixed Array — Allocates array of size W.

3. Optimal — FIFO Queue with Running Sum

Intuition

Enqueue new items. If queue length exceeds window size, dequeue front and deduct from running sum.

Algorithm

  1. Step 1: Enqueue incoming value and add it to windowSum.
  2. Step 2: If queue.size() > size, pop front element and subtract it from windowSum.
  3. Step 3: Return windowSum / queue.size().

FIFO Queue Moving Average Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Queue: [1]
Visual state
Values and pointers at this exact step
queue
FRONT → REAR
1
Enqueue adds at the rear · Dequeue removes from the front
Decision / next transition
next(1)
Why this step matters

Queue: [1]. Sum: 1. Avg: 1.0

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <queue>
3
4using namespace std;
5
6class MovingAverage {
7private:
8 queue<int> q;
9 int maxSize;
10 double windowSum;
11
12public:
13 MovingAverage(int size) : maxSize(size), windowSum(0.0) {}
14
15 double next(int val) {
16 q.push(val);
17 windowSum += val;
18
19 if (q.size() > maxSize) {
20 windowSum -= q.front();
21 q.pop();
22 }
23
24 return windowSum / q.size();
25 }
26};
27
28int main() {
29 MovingAverage ma(3);
30 cout << ma.next(1) << endl; // 1.0
31 cout << ma.next(10) << endl; // 5.5
32 cout << ma.next(3) << endl; // 4.66667
33 cout << ma.next(5) << endl; // 6.0
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(1) per call — A single push, optional pop, and running sum addition in strict O(1) time.
  • Space complexity: O(W) Queue Memory — Maintains at most W elements in queue.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Full Window RescanO(W) per next() callO(W)Store elements in a list. On every call, loop through the last W elements to compute sum and average.Iterating through all W elements on every stream tick.
2.Better — Circular Array Buffer with Head PointerO(1) per next()O(W) (Fixed Array)Use a fixed array of size W. Overwrite the slot at head % W after subtracting its old value from sum.None.
3.Optimal — FIFO Queue with Running Sum AccumulatorOptimalO(1) per next()O(W)Enqueue new element and add to sum. If queue size > W, dequeue front and subtract from sum. Return sum / size.None. Constant time.

Common Pitfalls & Crucial Edge Cases

Dividing by capacity when queue is partially full

Divisor must be queue.size(), not size.

Accumulating integer truncation

Use double/float precision for sum to avoid integer division truncation.

Crucial Edge Cases to Validate:

  • Stream length less than window size — Divides by actual current queue length rather than window capacity.
  • Negative numbers — Floating point addition and subtraction handle signed integer arithmetic without special casing.
  • Zero values — Correctly contributes 0 to sum while increasing the count denominator.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention floating-point precision: IEEE 754 precision drift over billions of additions/subtractions can be periodically reset in production systems.
  2. Discuss circular buffer vs Queue: circular buffer avoids heap allocations in garbage-collected languages.
  3. Discuss numerical stability and precision drift over long-running streams as a practical engineering trade-off.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the time complexity of next() using the FIFO queue with running sum?

2.What should the divisor be if window size is 5, but only 2 numbers have arrived so far?

3.What happens to the running sum when an element is evicted?

Back to DSA Sheet