Problem

Given a stream of numbers, calculate moving average

Similar problem - Moving Average of Last N numbers in a Stream

Solution

Method 1 - Simple Maths

This is straightforward math. If we have seen a total of n numbers so far, and the current average is avg, when a new element is added, the new average can be calculated as avg = (n * avg + new_element) / (n + 1). Below is the pseudocode to compute the moving average of all numbers in a stream in O(1) time:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

avg = 0;
n = 0;

def add(element):
  avg = (n*avg)/(n+1);
  n++;
end

def getAvg()
  return avg;
end
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class MovingAverage {
	// Prints average of a
	// stream of numbers
	 void add(int x) {
		sum += x;
		n++;
	}

	public double getAvg(int x) {
		return (((double) sum) / n);
	}
}
 
1
2
3
4
5
6
7

nums = [....]; // number stream
List<Integer> ans = new LinkedList<>();
var mAvg = new MovingAverage();
for(int num: nums) {
	mAvg.add(num);
	ans.add(mAvg.getAvg());
}