Moving Average from Data Stream
Moving Average from Data Stream is a easy design data structures problem solved with the queue / circular buffer pattern.
The best approach, optimal (circular buffer with a running sum), runs in O(1) per call time and O(size) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (re-sum the window every call) up.
Problem
Design a class MovingAverage that receives a stream of integers and reports the average of the most recent size values.
MovingAverage(int size)creates the object with window sizesize.double next(int val)addsvalto the stream and returns the average of the lastsizevalues (or of all values so far, if fewer thansizehave arrived).
Examples
Example 1
- Input
MovingAverage(3), next(4), next(10), next(1), next(7)- Output
4.0, 7.0, 5.0, 6.0- Why
- Until 3 values have arrived the average uses all of them; after that only the last 3 count: (10 + 1 + 7) / 3 = 6.
Example 2
- Input
MovingAverage(1), next(5), next(-3)- Output
5.0, -3.0- Why
- With a window of 1, the average is always the latest value.
Constraints
1 <= size <= 1000-10^5 <= val <= 10^5- At most
10^4calls tonext. - Answers within
10^-5of the true average are accepted.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (re-sum the window every call) | O(size) per call | O(calls) |
| Optimal (circular buffer with a running sum) | O(1) per call | O(size) |
1Brute force (re-sum the window every call)
O(size) per callEach call loops over up to size stored values.O(calls)Every value is kept, even ones that left the window.Store every value ever received. On each call, add up the last min(size, count) values and divide.
- Append val to a list.
- Let k = min(size, list length); sum the last k values.
- Return sum / k as a double.
class MovingAverage {
private final int size;
private final List<Integer> values = new ArrayList<>();
public MovingAverage(int size) {
this.size = size;
}
public double next(int val) {
values.add(val);
int k = Math.min(size, values.size());
long sum = 0;
for (int i = values.size() - k; i < values.size(); i++) sum += values.get(i);
return (double) sum / k;
}
}class MovingAverage:
def __init__(self, size: int):
self.size = size
self.values = []
def next(self, val: int) -> float:
self.values.append(val)
k = min(self.size, len(self.values))
total = 0
for i in range(len(self.values) - k, len(self.values)):
total += self.values[i]
return total / kclass MovingAverage {
int size;
vector<int> values;
public:
MovingAverage(int size) : size(size) {}
double next(int val) {
values.push_back(val);
int k = min(size, (int)values.size());
long long sum = 0;
for (int i = values.size() - k; i < (int)values.size(); i++) sum += values[i];
return (double)sum / k;
}
};class MovingAverage {
constructor(size) {
this.size = size;
this.values = [];
}
next(val) {
this.values.push(val);
const k = Math.min(this.size, this.values.length);
let sum = 0;
for (let i = this.values.length - k; i < this.values.length; i++) sum += this.values[i];
return sum / k;
}
}2Optimal (circular buffer with a running sum)
O(1) per callA constant number of operations per call.O(size)Only the last size values are stored.Keep a fixed array of size slots used as a ring, a write position, how many values are in it, and the sum of those values. A new value overwrites the oldest slot once the ring is full, so the sum is fixed with one subtraction and one addition.
- If count == size, subtract buf[pos] (the oldest value) from the sum; otherwise count++.
- Write val into buf[pos], add it to the sum and advance pos = (pos + 1) % size.
- Return sum / count.
class MovingAverage {
private final int[] buf;
private int pos = 0, count = 0;
private long sum = 0;
public MovingAverage(int size) {
buf = new int[size];
}
public double next(int val) {
if (count == buf.length) sum -= buf[pos];
else count++;
buf[pos] = val;
sum += val;
pos = (pos + 1) % buf.length;
return (double) sum / count;
}
}class MovingAverage:
def __init__(self, size: int):
self.buf = [0] * size
self.pos = 0
self.count = 0
self.total = 0
def next(self, val: int) -> float:
if self.count == len(self.buf):
self.total -= self.buf[self.pos]
else:
self.count += 1
self.buf[self.pos] = val
self.total += val
self.pos = (self.pos + 1) % len(self.buf)
return self.total / self.countclass MovingAverage {
vector<int> buf;
int pos = 0, count = 0;
long long sum = 0;
public:
MovingAverage(int size) : buf(size, 0) {}
double next(int val) {
if (count == (int)buf.size()) sum -= buf[pos];
else count++;
buf[pos] = val;
sum += val;
pos = (pos + 1) % buf.size();
return (double)sum / count;
}
};class MovingAverage {
constructor(size) {
this.buf = new Array(size).fill(0);
this.pos = 0;
this.count = 0;
this.sum = 0;
}
next(val) {
if (this.count === this.buf.length) this.sum -= this.buf[this.pos];
else this.count++;
this.buf[this.pos] = val;
this.sum += val;
this.pos = (this.pos + 1) % this.buf.length;
return this.sum / this.count;
}
}Edge cases to test
- Fewer values than the window size so far (divide by the count, not by size)
- Window size 1
- Negative values and an average that is not a whole number
Hints
Hint 1
Only the last size values matter. Which value leaves the window when a new one arrives?
Hint 2
Keep the window's running sum: add the new value and subtract the one that falls out, instead of re-adding the whole window.
FAQ
What is the best time complexity for Moving Average from Data Stream?
Optimal (circular buffer with a running sum) runs in O(1) per call time and O(size) extra space. A constant number of operations per call.
Which pattern does Moving Average from Data Stream use?
It is a design data structures problem that uses the queue / circular buffer pattern. Other problems with the same pattern: Design Hit Counter, Design Circular Queue, First Unique Number.
Is there a brute force solution for Moving Average from Data Stream?
Yes. Brute force (re-sum the window every call) takes O(size) per call time and O(calls) space. Store every value ever received.
Which edge cases should I test for Moving Average from Data Stream?
Fewer values than the window size so far (divide by the count, not by size); Window size 1; Negative values and an average that is not a whole number.