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.

Examples

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.

Thinking Process

  1. Sliding window pattern: Queue naturally maintains FIFO order
  • Maintain a window [left, right] satisfying a constraint.
  • Expand right to grow; shrink left when invalid.
  • Fixed window: slide both pointers together.
Sliding window a b c d e window expand right, shrink left when invalid

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Fixed-size window (this problem) O(n) O(1) Window size known upfront
Variable-size window O(n) O(1) Expand/shrink until valid
Window + hash map O(n) O(k) Track character/count frequencies
Deque window max O(n) O(k) Monotonic deque for max/min in window

Solution

Time Complexity: O(1) per next() call
Space Complexity: O(size) - Queue stores at most size elements

This solution uses a queue to maintain the sliding window and a running sum to calculate the average efficiently.

class MovingAverage:
deque[int> q
windowSize
long long windowSum
MovingAverage(size) :
windowSize = size
windowSum = 0
def next(self, val):
    q.push(val)
    windowSum += val
    if len(q) > windowSize:
        windowSum -= q[0]
        q.pop()
    return (double) windowSum / len(q)
/
 Your MovingAverage object will be instantiated and called as such:
 MovingAverage obj = new MovingAverage(size)
 double param_1 = obj.next(val)
/

Solution Explanation

Approach: Fixed-size window (this problem)

Key idea: 1. Sliding window pattern: Queue naturally maintains FIFO order

How the code works:

  1. Sliding window pattern: Queue naturally maintains FIFO order
    • Maintain a window [left, right] satisfying a constraint.
    • Expand right to grow; shrink left when invalid.
    • Fixed window: slide both pointers together.
Operation Time Space
Constructor O(1) O(1)
next() O(1) O(size)
Overall O(1) per call O(size)

How Solution 1 Works

  1. Initialization:
    • Store windowSize to know the maximum window size
    • Initialize windowSum to 0
  2. Adding new value:
    • Push new value to queue
    • Add value to running sum
  3. Maintaining window size:
    • If queue size exceeds windowSize, remove oldest element
    • Subtract removed element from running sum
  4. Calculate average:
    • Return windowSum / q.size()
    • Note: q.size() may be less than windowSize initially

Key Insight

  • Running sum: Maintain sum of current window elements
  • Queue: Automatically maintains FIFO order for sliding window
  • O(1) average calculation: No need to sum all elements each time

    Example Walkthrough

Input: size = 3, calls: next(1), next(10), next(3), next(5)

Solution 1 (Queue):

Initial: q = [], windowSum = 0

next(1):
  q.push(1) → q = [1]
  windowSum = 0 + 1 = 1
  q.size() = 1
  return 1.0 / 1 = 1.0

next(10):
  q.push(10) → q = [1, 10]
  windowSum = 1 + 10 = 11
  q.size() = 2
  return 11.0 / 2 = 5.5

next(3):
  q.push(3) → q = [1, 10, 3]
  windowSum = 11 + 3 = 14
  q.size() = 3 (equals windowSize)
  return 14.0 / 3 = 4.66667

next(5):
  q.push(5) → q = [1, 10, 3, 5]
  windowSum = 14 + 5 = 19
  q.size() = 4 > windowSize
  Remove q.front() = 1
  windowSum = 19 - 1 = 18
  q.pop() → q = [10, 3, 5]
  return 18.0 / 3 = 6.0

Complexity

| Operation | Time | Space | |———–|——|——-| | Constructor | O(1) | O(1) | | next() | O(1) | O(size) | | Overall | O(1) per call | O(size) |

Common Mistakes

  1. Window not full: First few calls when q.size() < windowSize
  2. Single element window: size = 1
  3. Large window size: size = 1000
  4. Negative values: val = -10^5

  5. Many calls: Up to 10^4 calls

  6. Integer overflow: Using int for windowSum instead of long long
  7. Division by zero: Not handling case when queue is empty (shouldn’t happen per constraints)
  8. Wrong average: Using windowSize instead of q.size() when window not full
  9. Not removing old elements: Forgetting to pop when window is full
  10. Type conversion: Not casting to double before division

Optimization Tips

  1. Use long long: Prevents overflow when summing many values
  2. Queue vs Array: Queue is simpler, array is faster for fixed-size windows
  3. Early return: Can optimize for size = 1 case separately

Pattern Recognition

This problem demonstrates the “Sliding Window with Running Sum” pattern:

1. Use queue/array to maintain window
2. Maintain running sum of window elements
3. Add new element, update sum
4. Remove old element when window exceeds size
5. Calculate result from running sum

Similar problems:

  • Sliding Window Maximum
  • Sliding Window Median
  • Maximum Average Subarray
  • Subarray Sum Equals K

Real-World Applications

  1. Stock Price Analysis: Calculate moving average of stock prices
  2. Network Monitoring: Average network latency over time window
  3. Sensor Data: Smooth sensor readings over time
  4. Performance Metrics: Average response time in sliding window
  5. Signal Processing: Moving average filter for noise reduction

    References

Key Takeaways

  1. Sliding window pattern: Queue naturally maintains FIFO order
  2. Running sum optimization: Avoid recalculating sum each time
  3. Window size management: Check size before removing elements
  4. Type safety: Use long long to prevent overflow with large sums