Problem

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

OR

Design a class to calculate moving average of last N numbers in a stream of real numbers

Examples

1
2
3
4
5

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

Solution

We need to design a system that, upon receiving a new element in a stream, can compute the average of the last N elements in O(1) time. For instance, if the stream is updated with 3 after receiving 0, the moving average would be calculated as (-3+0+3)/3 = 0.0.

To address this, let’s define a class with two methods allowing us to add a number to the moving average and retrieve the average in O(1) time:

1
2
3
4

public interface MovingAverage{
 public void add(double num);
 public double getAvg();
}

First, we need to understand how to compute the moving average of all numbers seen so far in the stream.

In the Leetcode problem, the interface differs slightly:

1
2
3

public interface MovingAverage{
 public double next(int num);
}

Here, the moving average is returned immediately after adding the number.

Method 1 - Using Queue

This problem is solved by using a queue.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public class MovingAverage {
	LinkedList<Integer> queue;
	int size;
	double avg;

	/** Initialize your data structure here. */
	public MovingAverage(int size) {
		this.queue = new LinkedList<Integer> ();
		this.size = size;
	}

	public double next(int val) {
		if (queue.size()<this.size) {
			queue.offer(val);
			int sum = 0;
			for (int i: queue) {
				sum += i;
			}
			avg = (double) sum / queue.size();

			return avg;
		} else {
			int head = queue.poll();
			double minus = (double) head / this.size;
			queue.offer(val);
			double add = (double) val / this.size;
			avg = avg + add - minus;
			return avg;
		}
	}
}
 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class MovingAverage {

    Queue<Integer> q;
    double sum = 0;
    int size;

    public MovingAverage(int s) {
        q = new LinkedList();
        size = s;
    }

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

Method 2 - Circular Queue OR Array OR Buffer

This is a classical sliding window problem, where we need to compute the sum of a sliding window of size N. The average is then simply sliding_sum/N.

To implement the sliding sum, we can use a circular buffer of size N to hold the window. Each time we encounter a new element, we append it to the buffer until it is full. Once the buffer is full, we slide the head of the window by one position to the right, i.e., increment by one. As it’s a circular buffer, the head can be incremented using head=(head+1)%N. When a new element arrives, the free slot for it will be the previous slot of the head in the circular buffer, i.e., empty_slot=(N+head-1)%N. The following figures illustrate this concept:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

window of size 5 using circular buffer
free_slot  head
 |  |
 v  v
 |__|__|__|__|__|

 free_slot  head
 |  |
 v  v
 |__|__|__|__|__|

 head       free_slot
 |          |
 v          v
 |__|__|__|__|__|

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class MovingAverage {
    int[] window;
    int count;
    int capacity;
    int insertIdx;
    int sum;

    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        window = new int[size];
        count = 0;
        capacity = size;
        insertIdx = 0;
        sum = 0;
    }

    public double next(int val) {
        if (count < capacity) {
            count++;
        } else {
            sum -= window[insertIdx];
        }
        window[insertIdx] = val;
        sum += val;
        insertIdx = (insertIdx + 1) % capacity;
        int size = count;//at one point count = capacity
        return 1.0 * sum / size;
    }
}
 
1
2
3
4

public interface MovingAverage{
    public void add(double num);
    public double getAvg();
}