Moving Average from Data Stream - Practice Coding Problems

Moving Average from Data Stream - Problem

Design a class to calculate the moving average of a stream of integers over a sliding window of a specified size.

Implement the MovingAverage class:

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

The moving average is calculated by taking the sum of all values in the current window and dividing by the number of values in the window.

Input & Output

Example 1 — Basic Moving Average

$ Input: operations = [["MovingAverage",3],["next",1],["next",10],["next",3],["next",5]]

› Output: [null,1.0,5.5,4.666666666666667,6.0]

💡 Note: Initialize with window size 3. Add 1 → avg=1.0, add 10 → avg=(1+10)/2=5.5, add 3 → avg=(1+10+3)/3=4.67, add 5 → avg=(10+3+5)/3=6.0

Example 2 — Single Element Window

$ Input: operations = [["MovingAverage",1],["next",2],["next",8]]

› Output: [null,2.0,8.0]

💡 Note: Window size 1 means only current value matters. Add 2 → avg=2.0, add 8 → avg=8.0

Example 3 — Larger Window

$ Input: operations = [["MovingAverage",5],["next",1],["next",2],["next",3]]

› Output: [null,1.0,1.5,2.0]

💡 Note: Window size 5 but only 3 values added. Add 1 → avg=1.0, add 2 → avg=(1+2)/2=1.5, add 3 → avg=(1+2+3)/3=2.0

Constraints

1 ≤ size ≤ 1000
-10⁵ ≤ val ≤ 10⁵
At most 10⁴ calls to next

Visualization

Tap to expand

Understanding the Visualization

Input Stream

Stream of integers: [1, 10, 3, 5] with window size 3

Sliding Window

Maintain last 3 values and calculate their average

Output

Return averages: [1.0, 5.5, 4.67, 6.0]

Key Takeaway

🎯 Key Insight: Use a queue to maintain the sliding window and keep a running sum to achieve O(1) time complexity per operation

Asked in

G Google 25 a Amazon 18 f Facebook 12 M Microsoft 15

The key insight is to maintain a sliding window using a queue and keep a running sum to avoid recalculating the total each time. The optimal approach uses a queue to store exactly the window size elements and tracks the running sum, achieving O(1) time per operation. Time: O(1), Space: O(k) where k is window size.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Queue with Running Sum	O(1)	O(k)	Use queue to maintain window and running sum to avoid recalculation
Brute Force - Store All Values	O(k)	O(n)	Store all values and recalculate average from scratch each time

Optimized - Queue with Running Sum — Algorithm Steps

Check if queue is at capacity
If full, remove oldest value and subtract from running sum
Add new value to queue and running sum
Return running sum divided by queue size

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Capacity

If queue full, remove oldest and update sum

Add New

Add new value to queue and running sum

Calculate

Return running sum divided by queue size

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int size;
    int* queue;
    int front;
    int rear;
    int count;
    double runningSum;
} MovingAverage;

MovingAverage* movingAverageCreate(int size) {
    MovingAverage* ma = (MovingAverage*)malloc(sizeof(MovingAverage));
    ma->size = size;
    ma->queue = (int*)malloc(size * sizeof(int));
    ma->front = 0;
    ma->rear = 0;
    ma->count = 0;
    ma->runningSum = 0.0;
    return ma;
}

double movingAverageNext(MovingAverage* ma, int val) {
    if (ma->count == ma->size) {
        // Remove oldest value
        int oldVal = ma->queue[ma->front];
        ma->runningSum -= oldVal;
        ma->front = (ma->front + 1) % ma->size;
        ma->count--;
    }
    
    // Add new value
    ma->queue[ma->rear] = val;
    ma->rear = (ma->rear + 1) % ma->size;
    ma->count++;
    ma->runningSum += val;
    
    return ma->runningSum / ma->count;
}

int main() {
    printf("[null,1.0,5.5,4.666666666666667]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Each next() call does constant work: one addition, possibly one removal

✓ Linear Growth

Space Complexity

O(k)

Queue stores exactly k values where k is the window size

✓ Linear Space

32.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Queue with Running Sum — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler