346.Moving_Average_from_Data_Stream(Medium).md

346. Moving Average from Data Stream (Easy)

Date and Time: Dec 9, 2024, 21:17 (EST)

Link: https://leetcode.com/problems/moving-average-from-data-stream

Question:

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^5 <= val <= 10^5

• At most 10^4 calls will be made to next.

Walk-through:

1. Use deque[] to maintain k elements, and curSum to save the summation of k elements.

2. When len(deque) == size, we remove the left-most element from deque[] and curSum. Then we add val into deque[] and update curSum and return curSum / len(deque).

Python Solution:

class MovingAverage:
    # Maintain sliding window with size, when len(sliding) == size, remove the left most and add the right most

    # TC: O(1), SC: O(size)
    def __init__(self, size: int):
        self.deque = collections.deque()
        self.curSum, self.size = 0, size

    def next(self, val: int) -> float:
        if len(self.deque) == self.size:
            self.curSum -= self.deque.popleft()
        self.curSum += val
        self.deque.append(val)
        return self.curSum / len(self.deque)


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

Time Complexity: $O(1)$, we only run the function when next() is called.
Space Complexity: $O(n)$