# Moving Average from Data Stream

`Queue`, `Design`

Easy

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

Example:

``````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

#### Queue (Implemented with LinkedList)

(137ms 59.29%)

``````class MovingAverage {
private int sum;
private Queue<Integer> queue;
private int capacity;

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

public double next(int val) {
if (queue.size() == capacity) {
int sub = queue.poll();
sum = sum - sub;
}
queue.offer(val);
sum = sum + val;

return (double) sum / queue.size();
}
}

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

#### Another simplerimplementation using LinkedList as Queue

``````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();
}
}
``````
##### Using ArrayDeque
``````class MovingAverage {
Deque<Integer> q;
int sum;
int size;

/** Initialize your data structure here. */
public MovingAverage(int size) {
this.size = size;
sum = 0;
q = new ArrayDeque<Integer>();
}

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

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

#### Using fixed length Array (Circular Queue)

(74 ms, faster than 100.00%, 43 MB, less than 59.43%)

``````public class MovingAverage {
private int [] window;
private int n, insert;
private long sum;

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

public double next(int val) {
if (n < window.length)  n++;
sum -= window[insert];
sum += val;
window[insert] = val;
insert = (insert + 1) % window.length;

return (double)sum / n;
}
}
``````
##### Another implementation
``````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 = Math.min(count, capacity);
return 1.0 * sum / size;
}
}

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