# Question

Formatted question description: https://leetcode.ca/all/346.html

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:

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

Explanation
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3


Constraints:

• 1 <= size <= 1000
• -105 <= val <= 105
• At most 104 calls will be made to next.

# Algorithm

This first-in, first-out feature is most suitable for using queues, and we also need a double variable sum to record the sum of all current numbers.

After entering this new number,

• If the limit is not exceeded, sum plus this number,
• If it exceeds, then sum first subtracts the earliest number, then adds this number, and then returns the number of sum divided by the queue

# Code

• import java.util.LinkedList;

public class Moving_Average_from_Data_Stream {

public static void main(String[] args) {
Moving_Average_from_Data_Stream out = new Moving_Average_from_Data_Stream();
MovingAverage m = out.new MovingAverage(3);

System.out.println(m.next(1));
System.out.println(m.next(10));
System.out.println(m.next(3));
System.out.println(m.next(5));
}

public class MovingAverage {
int size;
double avg;

/** Initialize your data structure here. */
public MovingAverage(int size) {
this.size = size;
}

/** API: Return moving average. */
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 {
queue.offer(val);

double minus = (double) head / this.size;
double add = (double) val / this.size;

avg = avg + add - minus; // math

return avg;
}
}
}
}

############

class MovingAverage {
private int[] arr;
private int s;
private int cnt;

public MovingAverage(int size) {
arr = new int[size];
}

public double next(int val) {
int idx = cnt % arr.length;
s += val - arr[idx];
arr[idx] = val;
++cnt;
return s * 1.0 / Math.min(cnt, arr.length);
}
}

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

• // OJ: https://leetcode.com/problems/moving-average-from-data-stream/
// Time:
//     MovingAverage: O(1)
//     next: O(1)
// Space: O(S)
class MovingAverage {
private:
queue<int> q;
int size, sum = 0;
public:
MovingAverage(int size) : size(size) { }
double next(int val) {
q.push(val);
sum += val;
if (q.size() > size) {
sum -= q.front();
q.pop();
}
return (double)sum / q.size();
}
};

• class MovingAverage:
def __init__(self, size: int):
self.arr = [0] * size
self.s = 0
self.cnt = 0

def next(self, val: int) -> float:
idx = self.cnt % len(self.arr)
self.s += val - self.arr[idx]
self.arr[idx] = val
self.cnt += 1
return self.s / min(self.cnt, len(self.arr))

# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param_1 = obj.next(val)

############

from collections import deque

# with no sum variable, calculate on the fly
class MovingAverage:
def __init__(self, size: int):
self.queue = deque()
self.size = size
self.avg = 0

def next(self, val: int) -> float:
if len(self.queue) < self.size:
self.queue.append(val)
self.avg = sum(self.queue) / len(self.queue)
return self.avg
else:
self.queue.append(val)
self.avg = self.avg + add - minus
return self.avg

from collections import deque

class MovingAverage(object):

def __init__(self, size):
"""
:type size: int
"""
self.windowSize = size
self.windowSum = 0.0
self.data = deque([])

def next(self, val):
"""
:type val: int
:rtype: float
"""
self.windowSum += val
data = self.data

leftTop = 0
if len(data) >= self.windowSize:
leftTop = data.popleft()
data.append(val)

self.windowSum -= leftTop
if len(data) < self.windowSize:
return self.windowSum / len(data)
return self.windowSum / self.windowSize

# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param_1 = obj.next(val)


• type MovingAverage struct {
arr []int
cnt int
s   int
}

func Constructor(size int) MovingAverage {
arr := make([]int, size)
return MovingAverage{arr, 0, 0}
}

func (this *MovingAverage) Next(val int) float64 {
idx := this.cnt % len(this.arr)
this.s += val - this.arr[idx]
this.arr[idx] = val
this.cnt++
return float64(this.s) / float64(min(this.cnt, len(this.arr)))
}

func min(a, b int) int {
if a < b {
return a
}
return b
}

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