Practice/Google/Leetcode 346. Moving Average from Data Stream

Leetcode 346. Moving Average from Data Stream

CodingMust

Problem

You need to implement a data structure that calculates the average of the most recent values from a continuous data stream within a specified window size.

Your class should support the following operations:

• Constructor: Initialize the structure with a maximum window size k
• next(val): Add a new value to the stream and return the average of at most the last k values

The key challenge is to efficiently maintain this sliding window so that each operation runs in constant time, while keeping memory usage proportional to the window size.

Requirements

1. Implement a MovingAverage class with a constructor that accepts the window size
2. Implement a next(val) method that adds a value and returns the current moving average
3. The moving average should include at most the last k values
4. If fewer than k values have been added, compute the average of all values seen so far
5. Each next() operation should run in O(1) time
6. Space complexity should be O(k) where k is the window size

Constraints

• 1 ≤ window size ≤ 1000
• -10^5 ≤ val ≤ 10^5
• At most 10^4 calls will be made to next

Examples

Example 1:

MovingAverage m = new MovingAverage(3) m.next(1) → returns 1.0 // average of [1] m.next(10) → returns 5.5 // average of [1, 10] m.next(3) → returns 4.67 // average of [1, 10, 3] m.next(5) → returns 6.0 // average of [10, 3, 5] (window slides)

Example 2:

MovingAverage m = new MovingAverage(2) m.next(5) → returns 5.0 // average of [5] m.next(8) → returns 6.5 // average of [5, 8] m.next(3) → returns 5.5 // average of [8, 3] (window slides) m.next(9) → returns 6.0 // average of [3, 9]