Moving Average from Data Stream
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 ofsizevalues.next(int val)addsvalto the stream and returns the average of the lastsizevalues. Untilsizevalues 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; return1.0.next(10): the window holds 1, 10; return5.5.next(3): the window holds 1, 10, 3; return4.66667.next(5): the window holds 10, 3, 5; return6.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; return4.0.next(-7): the window holds −7; return-7.0.next(0): the window holds 0; return0.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; return5.0.next(6): the window holds 5, 6; return5.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:
next(1): the window holds 1. Adding them up gives 1, over 1: return 1.0.next(10): the window holds 1, 10. Adding them up gives 11, over 2: return 5.5.next(3): the window holds 1, 10, 3. Adding them up gives 14, over 3: return 4.66667.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
- Keep a list of every value.
- On
next(val): appendval, letcount = min(size, number of values), add up the lastcountvalues and return the sum divided bycount.
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:
next(1): add 1, and the total is 1 over 1: return 1.0.next(10): add 10, and the total is 11 over 2: return 5.5.next(3): add 3, and the total is 14 over 3: return 4.66667.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
- Start with an empty queue and
total = 0. - On
next(val): pushvaland add it tototal. - If the queue holds more than
sizevalues, pop the front and subtract it fromtotal. - Return
totaldivided 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.