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

Example:

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

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

Compute the Moving Average by using Array or List

The most intuitive method would be to use a vector/array/list to store the numbers. Then we can erase the begining (pop_front) if the size is larger than the window. Then we can go through the window to sum up and compute the moving average.

data-structure-window-queue

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
32
33

class MovingAverage {
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        sz = size;
        c = 0;
    }
    
    double next(int val) {
        if (c >= sz) {
            data.erase(data.begin());
            data.push_back(val);
        } else {
            data.push_back(val);
            c ++;
        }
        double r = 0;
        for (int i = 0; i < c; ++ i) {
            r += data[i];
        }
        return r / c;
    }
    
    vector<int> data;
    int sz;
    int c;
};
 
/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */

class MovingAverage {
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        sz = size;
        c = 0;
    }
    
    double next(int val) {
        if (c >= sz) {
            data.erase(data.begin());
            data.push_back(val);
        } else {
            data.push_back(val);
            c ++;
        }
        double r = 0;
        for (int i = 0; i < c; ++ i) {
            r += data[i];
        }
        return r / c;
    }
    
    vector<int> data;
    int sz;
    int c;
};

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */

The space complexity is O(W) where W is the size of the moving average window. And the time complexity is also O(W) as we need to iterate W times to compute the sum and thus the moving average.

Using Double-ended Queue to Compute the Moving Average in O(1) constant time

data-structure-deque

A better way to design the Moving Average class is to use deque (the double-ended queue). We also use a variable to store the sum of the moving average and update it when an element is pop from the begining of the queue and appended into the rear of the queue. Please note that the pop_front and push_back of the deque run at O(1) constant time – which makes the overall time complexity is O(1) and the space requirement is O(W) where we need to store all the numbers in the moving average window.

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

class MovingAverage {
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        M = size;
    }
    
    double next(int val) {
        if (data.size() < M) {
            data.push_back(val);
            sum += val;
            return (double)sum / data.size();
        }
        sum -= data[0];
        data.pop_front();
        sum += val;
        data.push_back(val);
        return (double)sum / data.size();
    }
private:
    deque<int> data;
    int M;
    int sum = 0;
};
 
/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage* obj = new MovingAverage(size);
 * double param_1 = obj->next(val);
 */

class MovingAverage {
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        M = size;
    }
    
    double next(int val) {
        if (data.size() < M) {
            data.push_back(val);
            sum += val;
            return (double)sum / data.size();
        }
        sum -= data[0];
        data.pop_front();
        sum += val;
        data.push_back(val);
        return (double)sum / data.size();
    }
private:
    deque<int> data;
    int M;
    int sum = 0;
};

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage* obj = new MovingAverage(size);
 * double param_1 = obj->next(val);
 */

–EOF (The Ultimate Computing & Technology Blog) —