Skip to main content
CodePeet

Moving Average from Data Stream

Try it yourself
EasyProblemExternal link

Description

A stream of integers arrives one at a time, and you want the average of the latest few. Build a MovingAverage:

  • MovingAverage(int size) starts with an empty stream and a window of size values.
  • next(int val) adds val to the stream and returns the average of the last size values. Until size values have arrived, it's the average of all of them.

Answers are compared rounded to 5 decimal places.

Examples

Example 1

Input:

["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]

Output: [null, 1.0, 5.5, 4.66667, 6.0]

Explanation:

  • MovingAverage(3): a window of 3.
  • next(1): the window holds 1; return 1.0.
  • next(10): the window holds 1, 10; return 5.5.
  • next(3): the window holds 1, 10, 3; return 4.66667.
  • next(5): the window holds 10, 3, 5; return 6.0.

The window holds up to 3 values. After 1, 10 and 3 it is full, so when 5 arrives the 1 leaves: (10 + 3 + 5) / 3 = 6.0.

Example 2

Input:

["MovingAverage", "next", "next", "next"]
[[1], [4], [-7], [0]]

Output: [null, 4.0, -7.0, 0.0]

Explanation:

  • MovingAverage(1): a window of 1.
  • next(4): the window holds 4; return 4.0.
  • next(-7): the window holds −7; return -7.0.
  • next(0): the window holds 0; return 0.0.

A window of 1 holds only the latest value.

Example 3

Input:

["MovingAverage", "next", "next"]
[[4], [5], [6]]

Output: [null, 5.0, 5.5]

Explanation:

  • MovingAverage(4): a window of 4.
  • next(5): the window holds 5; return 5.0.
  • next(6): the window holds 5, 6; return 5.5.

Fewer values than the window holds: average the ones there are.

Constraints

  • 1 ≤ size ≤ 1000
  • −10^5 ≤ val ≤ 10^5
  • At most 10^4 calls will be made to next

Editorial

Brute Force

Intuition

Keep every value. When one arrives, add up the last size of them, or all of them if there aren't that many yet, and divide by how many there were.

Step-by-Step Explanation

Let's trace a window of 3 with the values 1, 10, 3, 5:

  1. next(1): the window holds 1. Adding them up gives 1, over 1: return 1.0.
  2. next(10): the window holds 1, 10. Adding them up gives 11, over 2: return 5.5.
  3. next(3): the window holds 1, 10, 3. Adding them up gives 14, over 3: return 4.66667.
  4. next(5): the window holds 10, 3, 5. Adding them up gives 18, over 3: return 6.0.

Add Up the Window Every Time — The window is outlined; dim values are kept but no longer in it.

Algorithm

  1. Keep a list of every value.
  2. On next(val): append val, let count = min(size, number of values), add up the last count values and return the sum divided by count.

Code

class MovingAverage {
    int size;
    vector<int> values;                      // every value so far
public:
    MovingAverage(int size) : size(size) {}

    double next(int val) {
        values.push_back(val);
        int count = min(size, (int)values.size());
        long long total = 0;
        for (int i = values.size() - count; i < (int)values.size(); i++)
            total += values[i];              // add up the last `count` values again
        return (double)total / count;
    }
};

class MovingAverage:
    def __init__(self, size: int):
        self.size = size
        self.values = []                     # every value so far

    def next(self, val: int) -> float:
        self.values.append(val)
        count = min(self.size, len(self.values))
        total = 0
        for x in self.values[-count:]:       # add up the last `count` values again
            total += x
        return total / count

class MovingAverage {
    private final int size;
    private final List<Integer> values = new ArrayList<>();   // every value so far

    public MovingAverage(int size) {
        this.size = size;
    }

    public double next(int val) {
        values.add(val);
        int count = Math.min(size, values.size());
        long total = 0;
        for (int i = values.size() - count; i < values.size(); i++)
            total += values.get(i);                               // add up the last `count` values again
        return (double) total / count;
    }
}

var MovingAverage = function(size) {
    this.size = size;
    this.values = [];                        // every value so far
};

MovingAverage.prototype.next = function(val) {
    this.values.push(val);
    const count = Math.min(this.size, this.values.length);
    let total = 0;
    for (let i = this.values.length - count; i < this.values.length; i++)
        total += this.values[i];             // add up the last `count` values again
    return total / count;
};

Complexity Analysis

Time Complexity: O(size) per call

Each call adds up to size values.

Space Complexity: O(n)

Every value is kept, though only the last size are ever used.

Why This Approach Is Not Efficient

Here it still fits: at most 10^4 calls times a window of 1,000 is 10^7 additions, and the Python version used 1.17s of its 5s on our tests. But the cost of every call grows with the window, and almost all of it is repeated work: once the window is full, consecutive windows share size - 1 values, and each call adds them all up again.

Only two things change between calls: one value arrives and, once the window is full, one leaves, the oldest. So keep a running total. Add the new value, subtract the one that leaves, and to know which one leaves, keep the window in a queue.

Optimal Approach - A Queue and a Running Total

Intuition

Keep the window's values in a queue, oldest first, and their sum in total. A new value joins the back and is added to total. If the queue now holds more than size values, the front is the one that just slid out: pop it and subtract it. The average is total divided by the queue's length.

Step-by-Step Explanation

Let's trace a window of 3 with the values 1, 10, 3, 5:

  1. next(1): add 1, and the total is 1 over 1: return 1.0.
  2. next(10): add 10, and the total is 11 over 2: return 5.5.
  3. next(3): add 3, and the total is 14 over 3: return 4.66667.
  4. next(5): add 5; the queue holds 4, one too many, so 1 leaves and is subtracted. The total is 18 over 3: return 6.0.

One In, One Out — The queue holds the values from head on; the orange one has just left, and its value left the total with it.

Algorithm

  1. Start with an empty queue and total = 0.
  2. On next(val): push val and add it to total.
  3. If the queue holds more than size values, pop the front and subtract it from total.
  4. Return total divided by the queue's length.

Code

The total is a 64-bit integer in C++ and Java: 1,000 values of 10^5 fit in 32 bits, but there's no need to cut it close, and dividing it as a double gives the exact average up to rounding. JavaScript keeps an array and a head index instead of calling shift().

class MovingAverage {
    int size;
    queue<int> window;                       // the latest values, oldest first
    long long total = 0;                     // their sum, kept as values come and go
public:
    MovingAverage(int size) : size(size) {}

    double next(int val) {
        window.push(val);
        total += val;
        if ((int)window.size() > size) {     // one too many: the oldest leaves
            total -= window.front();
            window.pop();
        }
        return (double)total / window.size();
    }
};

from collections import deque

class MovingAverage:
    def __init__(self, size: int):
        self.size = size
        self.window = deque()                # the latest values, oldest first
        self.total = 0                       # their sum, kept as values come and go

    def next(self, val: int) -> float:
        self.window.append(val)
        self.total += val
        if len(self.window) > self.size:     # one too many: the oldest leaves
            self.total -= self.window.popleft()
        return self.total / len(self.window)

class MovingAverage {
    private final int size;
    private final Deque<Integer> window = new ArrayDeque<>();   // the latest values, oldest first
    private long total = 0;                                     // their sum, kept as values come and go

    public MovingAverage(int size) {
        this.size = size;
    }

    public double next(int val) {
        window.offerLast(val);
        total += val;
        if (window.size() > size) total -= window.pollFirst();   // one too many: the oldest leaves
        return (double) total / window.size();
    }
}

var MovingAverage = function(size) {
    this.size = size;
    this.values = [];                        // every value, in order
    this.head = 0;                           // the oldest one still inside the window
    this.total = 0;                          // the window's sum, kept as values come and go
};

MovingAverage.prototype.next = function(val) {
    this.values.push(val);
    this.total += val;
    if (this.values.length - this.head > this.size) {   // one too many: the oldest leaves
        this.total -= this.values[this.head];
        this.head++;
    }
    return this.total / (this.values.length - this.head);
};

Complexity Analysis

Time Complexity: O(1) per call

One push, one addition and at most one pop and subtraction, whatever the window's size.

Space Complexity: O(size)

The queue never holds more than size values. (The JavaScript version's array keeps the old values too; a ring buffer of size slots would not.)

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Dividing by the size from the first call. return self.total / self.size

With a window of 4, on next(9), next(1) it returns 2.25, 2.5; the answers are 9.0, 5.0. Until size values have arrived, the window holds fewer than size of them, and the average is over the ones there are. Divide by the window's length, not by size.

Dividing with //. return self.total // len(self.window)

With a window of 3, on next(10), next(3), next(4) it returns 10.0, 6.0, 5.0; the answers are 10.0, 6.5, 5.66667. // drops the fraction, so the average of 10, 3 and 4 comes out as 5 instead of 5.66667. The average is a real number: divide with /.

Forgetting to subtract the value that leaves. self.window.popleft()

With a window of 2, on next(1), next(2), next(3), next(4) it returns 1.0, 1.5, 3.0, 5.0; the answers are 1.0, 1.5, 2.5, 3.5. The oldest value is dropped from the queue but stays in the running total, so once the window is full the total keeps every value ever seen. Subtract what leaves.

Where This Pattern Is Taught

This problem practises a queue as a sliding window. It's taught in Introduction to Queues, next to Number of Recent Calls, which keeps its window by time instead of by size.