Welcome to Subscribe On Youtube

346. Moving Average from Data Stream

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:

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.

Solutions

This solution implements a moving average data structure that supports a method next(val) where val is an integer representing the next number in the data stream.

Class Initialization: __init__(self, size: int)

  • self.arr: Initializes an array of length size filled with zeros. This array serves as a circular buffer to hold the last N values inserted, where N is the specified size.
  • self.s: Initializes the sum of numbers currently in the circular buffer to 0. This sum is used to efficiently compute the moving average.
  • self.cnt: A counter to keep track of the total number of values that have been inserted so far. It helps in managing the circular nature of self.arr and calculating the average correctly during the initial phase when the buffer is not yet full.

Method: next(self, val: int) -> float

  • Circular Array Indexing: idx = self.cnt % len(self.arr) calculates the index at which the new value should be inserted. This calculation ensures that the array is used as a circular buffer, overwriting the oldest data points with new ones once the buffer size (size) is exceeded.
  • Updating Sum: The new value val is added to self.s, and the value being overwritten in self.arr is subtracted from self.s. This keeps self.s as the sum of all numbers currently in the buffer.
  • Inserting New Value: The new value val is stored in the array at the calculated index idx.
  • Incrementing Counter: The counter self.cnt is incremented by 1 to reflect the insertion of a new data point.
  • Calculating and Returning Moving Average: The method returns the moving average of the last N values. It divides self.s by min(self.cnt, len(self.arr)) to ensure the correct average is calculated:
    • During the initial phase (when fewer than N values have been inserted), it divides by self.cnt to average only the values that have been inserted.
    • Once the buffer is full (self.cnt >= N), it divides by len(self.arr) (N) to calculate the average of the last N values.
  • 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);
 */

  • class MovingAverage {
public:
    MovingAverage(int size) {
        arr.resize(size);
    }

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

private:
    vector<int> arr;
    int cnt = 0;
    int s = 0;
};

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

  • 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) # circular array
        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)))
}

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

All Problems

All Solutions