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
-10⁵ <= val <= 10⁵
At most 10⁴ 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 {
        LinkedList<Integer> queue;
        int size;
        double avg;

        /** Initialize your data structure here. */
        public MovingAverage(int size) {
            this.queue = new LinkedList<Integer>();
            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 {
                int head = queue.poll();
                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:
            head = self.queue.popleft()
            self.queue.append(val)
            minus = head / self.size
            add = val / self.size
            self.avg = self.avg + add - minus
            return self.avg


from collections import deque

class MovingAverage(object):

  def __init__(self, size):
    """
    Initialize your data structure here.
    :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);
 */

346 - Moving Average from Data Stream

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions