# 346 Moving Average from Data Stream

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.
For example,
MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3
The Idea: Using a queue is a great way of maintaining top `k` most current values since evicting the front of the queue means evicting the oldest element of the queue.
Complexity: O(K) space, O(1) time.
class MovingAverage {
public:
MovingAverage(int size) : window(size) {
cur_sum = 0;
count = 0;
};
double next(int val)
{
if (count < window) {
return next_init(val);
}
else {
cur_sum -= q.front();
q.pop();
q.push(val);
cur_sum += val;
return cur_sum / window;
}
}
private:
queue<int> q;
unsigned count;
double cur_sum;
int window;
double next_init(int val)
{
q.push(val);
cur_sum += val;
return cur_sum / ++count;
}
};
Python Solution
import queue
class MovingAverage:
def __init__(self, size):
self.q = queue.Queue()
self.cur_sum = 0
self.window = size
def next(self, val):
if self.q.qsize() == self.window:
old = self.q.get()
self.cur_sum -= old
self.q.put(val)
self.cur_sum += val
return self.cur_sum / self.q.qsize()