Description

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

Implement the MovingAverage class:

  • MovingAverage(int size) Initializes the object with the size of the window size.
  • double next(int val) Returns the moving average of the last size values of the stream.

Example 1:

 1Input
 2["MovingAverage", "next", "next", "next", "next"]
 3[[3], [1], [10], [3], [5]]
 4Output
 5[null, 1.0, 5.5, 4.66667, 6.0]
 6
 7Explanation
 8MovingAverage movingAverage = new MovingAverage(3);
 9movingAverage.next(1); // return 1.0 = 1 / 1
10movingAverage.next(10); // return 5.5 = (1 + 10) / 2
11movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
12movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3

Constraints:

  • 1 <= size <= 1000
  • -10^5 <= val <= 10^5
  • At most 10^4 calls will be made to next.

Solution

This is yet another Queue problem where we need FIFO structure. We want to add new elements at one end but those are also the ones which will be removed once the size is size.

Using Array or LinkedList

In order to implement this, we could use array or linkedlist.

 1class MovingAverage {
 2    private int size;
 3    List<Integer> queue;
 4
 5    public MovingAverage(int size) {
 6        this.size = size;
 7        queue = new ArrayList<>();
 8    }
 9
10    public double next(int val) {
11        queue.add(val);
12        int windowSum = 0;
13        int windowSize = Math.min(size, queue.size());
14        for (int i = queue.size() - windowSize; i < queue.size(); i++) {
15            windowSum += queue.get(i);
16        }
17        return windowSum / (double) windowSize;
18    }
19}
  • Time Complexity: O(n * k): where n = size of the moving window and k = number of elements elements added to queue.
  • Space Complexity: O(k) where k= number of elements added to the queue.

Using ArrayDeque

We could use one of the built-in classes in Java ArrayDeque to behave like a queue. In this case, every time we add new element, we also have to remove an element from the beginning of the queue when our queue is bigger than the window size. If this is not the case, we can simply return 0.

 1class MovingAverage {
 2    int size;
 3    int windowSum = 0;
 4    int count = 0;
 5    Deque<Integer> queue = new ArrayDeque<>();
 6
 7    public MovingAverage (int size) {
 8        this.size = size;
 9    }
10
11    public double next(int val) {
12        count++;
13        queue.add(val);
14        int tail = count > size ? (int) queue.poll() : 0;
15        windowSum = windowSum - tail + val;
16        return (double) windowSum / Math.min(size, count);
17    }
18}
  • Time Complexity: O(1) since adding an element to ArrayDeque is constant time operation.
  • Space Complexity: O(n) where n = size of the moving window