Skip to content

346. Moving Average from Data Stream 👍

  • Time: $O(1)$
  • Space: $O(size)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class MovingAverage {
 public:
  MovingAverage(int size) : size(size) {}

  double next(int val) {
    if (q.size() == size)
      sum -= q.front(), q.pop();
    sum += val;
    q.push(val);
    return sum / q.size();
  }

 private:
  int size;
  double sum = 0;
  queue<int> q;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class MovingAverage {
  public MovingAverage(int size) {
    this.size = size;
  }

  public double next(int val) {
    if (q.size() == size)
      sum -= q.poll();
    sum += val;
    q.offer(val);
    return sum / q.size();
  }

  private int size = 0;
  private double sum = 0;
  private Queue<Integer> q = new ArrayDeque<>();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class MovingAverage:
  def __init__(self, size: int):
    self.size = size
    self.sum = 0
    self.q = collections.deque()

  def next(self, val: int) -> float:
    if len(self.q) == self.size:
      self.sum -= self.q.popleft()
    self.sum += val
    self.q.append(val)
    return self.sum / len(self.q)