346. Moving Average from Data Stream

Problem Description

You need to implement a class that calculates the moving average of a stream of integers within a sliding window of a fixed size.

The MovingAverage class should support two operations:

Constructor MovingAverage(int size): Initializes the object with a window size. This window will hold at most size recent values from the stream.
Method next(int val): Adds a new integer val to the stream and returns the average of the most recent values in the window. If the total number of values seen so far is less than the window size, it returns the average of all values seen so far.

For example, if the window size is 3:

After adding the first value, the average is just that value
After adding the second value, the average is of those two values
After adding the third value, the average is of all three values
After adding the fourth value, the window slides - it drops the first value and keeps only the most recent three values, then calculates their average

The solution uses a circular array approach where:

self.s maintains the sum of values currently in the window
self.data is a fixed-size array that stores the window values
self.cnt tracks the total number of values processed
When a new value arrives, it replaces the oldest value in the circular array at position cnt % size, and the sum is updated by adding the new value and subtracting the old value at that position
The average is calculated by dividing the sum by the minimum of cnt and size (to handle cases where fewer than size elements have been added)

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is that we need to efficiently maintain a sliding window of the most recent values and calculate their average. The naive approach would be to store all values in a queue, remove the oldest when the window is full, and recalculate the sum each time. However, this would require iterating through all window elements to compute the sum for each new value.

We can optimize this by recognizing that when the window slides, only two values change: one value leaves the window and one enters. Instead of recalculating the entire sum, we can maintain a running sum and simply update it by subtracting the leaving value and adding the entering value. This gives us O(1) time complexity for each operation.

The circular array technique comes from observing that we don't need to physically shift elements when the window slides. Since we always replace the oldest value with the newest one, we can treat our fixed-size array as circular. By using the modulo operator cnt % size, we can map any count to a position in our array. When cnt exceeds the array size, the index wraps around to the beginning, naturally overwriting the oldest values.

For example, with a window size of 3:

Position 0 stores the 1st, 4th, 7th, ... values
Position 1 stores the 2nd, 5th, 8th, ... values
Position 2 stores the 3rd, 6th, 9th, ... values

This pattern ensures that at any point, our array contains exactly the most recent min(cnt, size) values. By maintaining the sum incrementally with s += val - data[i], we avoid the need to traverse the array, making each update operation constant time.

Solution Implementation

1class MovingAverage: 2 """ 3 A class to calculate the moving average of a stream of integers. 4 Uses a circular buffer to maintain a sliding window of the most recent values. 5 """ 6 7 def __init__(self, size: int): 8 """ 9 Initialize the MovingAverage with a fixed window size. 10 11 Args: 12 size: The size of the moving average window 13 """ 14 self.window_sum = 0 # Running sum of values in the current window 15 self.window = [0] * size # Circular buffer to store window values 16 self.count = 0 # Total number of values seen so far 17 18 def next(self, val: int) -> float: 19 """ 20 Add a new value to the stream and return the current moving average. 21 22 Args: 23 val: The new integer value to add to the stream 24 25 Returns: 26 The moving average of the values in the current window 27 """ 28 # Calculate the index in the circular buffer 29 index = self.count % len(self.window) 30 31 # Update the running sum by removing the old value and adding the new one 32 self.window_sum += val - self.window[index] 33 34 # Store the new value in the circular buffer 35 self.window[index] = val 36 37 # Increment the total count 38 self.count += 1 39 40 # Calculate average based on actual window size (handles initial filling) 41 window_size = min(self.count, len(self.window)) 42 return self.window_sum / window_size 43 44 45# Your MovingAverage object will be instantiated and called as such: 46# obj = MovingAverage(size) 47# param_1 = obj.next(val) 48

1/** 2 * Class to calculate the moving average of a data stream 3 * Uses a circular array to maintain a sliding window of values 4 */ 5class MovingAverage { 6 private int sum; // Running sum of elements in the window 7 private int count; // Total number of elements added so far 8 private int[] window; // Circular array to store the sliding window 9 10 /** 11 * Constructor initializes the moving average calculator with a fixed window size 12 * @param size The size of the sliding window 13 */ 14 public MovingAverage(int size) { 15 window = new int[size]; 16 sum = 0; 17 count = 0; 18 } 19 20 /** 21 * Adds a new value to the data stream and returns the moving average 22 * @param val The new value to add to the stream 23 * @return The moving average of the current window 24 */ 25 public double next(int val) { 26 // Calculate the index in circular array using modulo 27 int index = count % window.length; 28 29 // Update sum: add new value and subtract the value being replaced 30 sum += val - window[index]; 31 32 // Store the new value at the calculated index 33 window[index] = val; 34 35 // Increment the total count 36 count++; 37 38 // Calculate average: divide sum by the smaller of count or window size 39 // This handles the case when we haven't filled the window yet 40 return (double) sum / Math.min(count, window.length); 41 } 42} 43 44/** 45 * Your MovingAverage object will be instantiated and called as such: 46 * MovingAverage obj = new MovingAverage(size); 47 * double param_1 = obj.next(val); 48 */ 49

1class MovingAverage { 2public: 3 /** 4 * Constructor: Initialize the moving average with a fixed window size 5 * @param size: The size of the sliding window 6 */ 7 MovingAverage(int size) { 8 window_.resize(size); 9 } 10 11 /** 12 * Add a new value to the data stream and return the moving average 13 * @param val: The new value to add 14 * @return: The average of the last 'size' values (or all values if fewer than 'size') 15 */ 16 double next(int val) { 17 // Calculate the position in the circular buffer using modulo 18 int index = count_ % window_.size(); 19 20 // Update the sum by removing the old value at this position and adding the new value 21 sum_ += val - window_[index]; 22 23 // Store the new value in the circular buffer 24 window_[index] = val; 25 26 // Increment the total count of values seen 27 ++count_; 28 29 // Calculate average: divide sum by the minimum of count and window size 30 // This handles the case when we have fewer elements than the window size 31 return static_cast<double>(sum_) / std::min(count_, static_cast<int>(window_.size())); 32 } 33 34private: 35 int sum_ = 0; // Running sum of values in the current window 36 int count_ = 0; // Total number of values processed 37 std::vector<int> window_; // Circular buffer to store the sliding window values 38}; 39 40/** 41 * Your MovingAverage object will be instantiated and called as such: 42 * MovingAverage* obj = new MovingAverage(size); 43 * double param_1 = obj->next(val); 44 */ 45

1// Global variables for moving average calculation 2let sum: number = 0; // Running sum of elements in the window 3let count: number = 0; // Total number of elements added 4let windowData: number[] = []; // Circular buffer to store window elements 5let windowSize: number = 0; // Maximum size of the sliding window 6 7/** 8 * Initializes the moving average with a given window size 9 * @param size - The maximum number of elements in the sliding window 10 */ 11function initMovingAverage(size: number): void { 12 // Reset all global variables 13 sum = 0; 14 count = 0; 15 windowSize = size; 16 // Initialize circular buffer with zeros 17 windowData = new Array(size).fill(0); 18} 19 20/** 21 * Adds a new value to the data stream and returns the moving average 22 * @param val - The new value to add to the stream 23 * @returns The average of the last 'size' elements (or all elements if less than 'size') 24 */ 25function next(val: number): number { 26 // Calculate the index in the circular buffer using modulo 27 const currentIndex: number = count % windowSize; 28 29 // Update the running sum by removing the old value and adding the new value 30 // When count < windowSize, windowData[currentIndex] is 0 (initialized value) 31 sum = sum + val - windowData[currentIndex]; 32 33 // Store the new value in the circular buffer 34 windowData[currentIndex] = val; 35 36 // Increment the total count of elements added 37 count++; 38 39 // Calculate average: divide by the minimum of count and window size 40 // This handles the case when we have fewer elements than the window size 41 const elementsInWindow: number = Math.min(count, windowSize); 42 return sum / elementsInWindow; 43} 44

Solution Approach

The solution implements a circular array to efficiently maintain a sliding window of values. Here's how each component works:

Data Structure Setup:

self.s: Maintains the running sum of all values currently in the window
self.data: A fixed-size array of length size that stores the window values
self.cnt: Counts the total number of values processed (not limited to window size)

Initialization (__init__ method):

def __init__(self, size: int):  self.s = 0 # Sum starts at 0  self.data = [0] * size # Pre-allocate array with zeros  self.cnt = 0 # No values processed yet

Adding Values (next method):

Calculate the circular index:
```
i = self.cnt % len(self.data)
```
This maps the current count to a position in the array. For example, if size=3 and cnt=5, then i = 5 % 3 = 2, so the new value goes to position 2, replacing whatever was there before.
Update the running sum:
```
self.s += val - self.data[i]
```
Before overwriting the old value at position i, we adjust the sum by removing the old value (self.data[i]) and adding the new value (val). This maintains the correct sum in constant time.
Store the new value:
```
self.data[i] = val
```
Replace the old value at position i with the new value.
Increment the counter:
```
self.cnt += 1
```
Track that we've processed one more value.
Calculate and return the average:
```
return self.s / min(self.cnt, len(self.data))
```
The divisor is min(self.cnt, len(self.data)) to handle two cases:
- When cnt < size: We haven't filled the window yet, so divide by cnt
- When cnt >= size: The window is full, so divide by size

Time Complexity: O(1) for each next operation since we only perform constant-time operations.

Space Complexity: O(size) for storing the window values in the array.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example with window size 3 and the sequence of values: 1, 10, 3, 5.

Initial State:

size = 3
s = 0 (running sum)
data = [0, 0, 0] (circular array)
cnt = 0 (values processed)

Step 1: next(1)

Calculate index: i = 0 % 3 = 0
Update sum: s = 0 + 1 - 0 = 1 (add new value 1, subtract old value at data[0] which is 0)
Store value: data[0] = 1, so data = [1, 0, 0]
Increment counter: cnt = 1
Calculate average: 1 / min(1, 3) = 1 / 1 = 1.0
Window contains: [1]

Step 2: next(10)

Calculate index: i = 1 % 3 = 1
Update sum: s = 1 + 10 - 0 = 11 (add new value 10, subtract old value at data[1] which is 0)
Store value: data[1] = 10, so data = [1, 10, 0]
Increment counter: cnt = 2
Calculate average: 11 / min(2, 3) = 11 / 2 = 5.5
Window contains: [1, 10]

Step 3: next(3)

Calculate index: i = 2 % 3 = 2
Update sum: s = 11 + 3 - 0 = 14 (add new value 3, subtract old value at data[2] which is 0)
Store value: data[2] = 3, so data = [1, 10, 3]
Increment counter: cnt = 3
Calculate average: 14 / min(3, 3) = 14 / 3 ≈ 4.67
Window contains: [1, 10, 3] (window is now full)

Step 4: next(5)

Calculate index: i = 3 % 3 = 0 (wraps around to beginning!)
Update sum: s = 14 + 5 - 1 = 18 (add new value 5, subtract old value at data[0] which is 1)
Store value: data[0] = 5, so data = [5, 10, 3]
Increment counter: cnt = 4
Calculate average: 18 / min(4, 3) = 18 / 3 = 6.0
Window contains: [10, 3, 5] (value 1 was replaced by 5)

Notice how in Step 4, the index wrapped around to 0, replacing the oldest value (1) with the newest value (5). The sum was efficiently updated by subtracting the old value and adding the new one, avoiding the need to recalculate the entire sum. The circular array ensures we always maintain exactly the most recent 3 values without shifting any elements.

Time and Space Complexity

Time Complexity: O(1)

The next method performs a constant number of operations:

Calculating the index i using modulo operation: O(1)
Updating the sum s by subtracting the old value and adding the new value: O(1)
Updating the array at index i: O(1)
Incrementing the counter: O(1)
Calculating and returning the average using division and min operation: O(1)

All operations are constant time, making the overall time complexity O(1) per call to next.

Space Complexity: O(n)

Where n is the size parameter passed to the constructor:

The data array is initialized with size elements, requiring O(size) space
The other instance variables (s, cnt) use O(1) space
Total space complexity is O(size) = O(n)

The implementation uses a circular buffer approach where old values are overwritten once the buffer is full, maintaining a fixed space usage regardless of how many times next is called.

Common Pitfalls

1. Integer Division Instead of Float Division

A common mistake is forgetting that in some programming languages (like Python 2 or C++), dividing two integers performs integer division, truncating the decimal part.

Incorrect approach:

# In Python 2 or when using // operator return self.window_sum // min(self.count, len(self.window)) # Wrong! Truncates decimal

Solution: Ensure you're using float division. In Python 3, the / operator automatically performs float division. In other languages, cast one operand to float:

# Python 3 (correct) return self.window_sum / min(self.count, len(self.window))  # For languages requiring explicit casting return float(self.window_sum) / min(self.count, len(self.window))

2. Incorrectly Handling the Initial Window Fill

Many implementations fail when the number of elements seen is less than the window size, dividing by the window size instead of the actual count.

Incorrect approach:

def next(self, val: int) -> float:  index = self.count % len(self.window)  self.window_sum += val - self.window[index]  self.window[index] = val  self.count += 1  return self.window_sum / len(self.window) # Wrong! Always divides by window size

Solution: Always use min(self.count, len(self.window)) as the divisor to handle both cases correctly.

3. Forgetting to Update the Sum Before Overwriting

A critical error is overwriting the old value in the circular buffer before subtracting it from the running sum.

Incorrect approach:

def next(self, val: int) -> float:  index = self.count % len(self.window)  self.window[index] = val # Overwrites old value first!  self.window_sum += val - self.window[index] # Now subtracts the NEW value  self.count += 1  return self.window_sum / min(self.count, len(self.window))

Solution: Always update the sum BEFORE overwriting the old value:

self.window_sum += val - self.window[index] # Subtract old value first self.window[index] = val # Then overwrite

4. Not Handling Edge Case of Size 0

If the window size is 0, the code will crash with division by zero or array allocation issues.

Solution: Add validation in the constructor:

def __init__(self, size: int):  if size <= 0:  raise ValueError("Window size must be positive")  self.window_sum = 0  self.window = [0] * size  self.count = 0

5. Using a Queue Instead of Circular Array

While using a queue (deque) works correctly, it's less efficient for this specific problem.

Less optimal approach:

from collections import deque  class MovingAverage:  def __init__(self, size: int):  self.queue = deque(maxlen=size)   def next(self, val: int) -> float:  self.queue.append(val)  return sum(self.queue) / len(self.queue) # O(n) operation!

Why circular array is better: The circular array approach maintains a running sum, achieving O(1) time complexity for each operation, while the queue approach requires O(n) time to calculate the sum each time.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What does the following code do?

1def f(arr1, arr2): 2 i, j = 0, 0 3 new_arr = [] 4 while i < len(arr1) and j < len(arr2): 5 if arr1[i] < arr2[j]: 6 new_arr.append(arr1[i]) 7 i += 1 8 else: 9 new_arr.append(arr2[j]) 10 j += 1 11 new_arr.extend(arr1[i:]) 12 new_arr.extend(arr2[j:]) 13 return new_arr 14

1public static List<Integer> f(int[] arr1, int[] arr2) { 2 int i = 0, j = 0; 3 List<Integer> newArr = new ArrayList<>(); 4 5 while (i < arr1.length && j < arr2.length) { 6 if (arr1[i] < arr2[j]) { 7 newArr.add(arr1[i]); 8 i++; 9 } else { 10 newArr.add(arr2[j]); 11 j++; 12 } 13 } 14 15 while (i < arr1.length) { 16 newArr.add(arr1[i]); 17 i++; 18 } 19 20 while (j < arr2.length) { 21 newArr.add(arr2[j]); 22 j++; 23 } 24 25 return newArr; 26} 27

1function f(arr1, arr2) { 2 let i = 0, j = 0; 3 let newArr = []; 4 5 while (i < arr1.length && j < arr2.length) { 6 if (arr1[i] < arr2[j]) { 7 newArr.push(arr1[i]); 8 i++; 9 } else { 10 newArr.push(arr2[j]); 11 j++; 12 } 13 } 14 15 while (i < arr1.length) { 16 newArr.push(arr1[i]); 17 i++; 18 } 19 20 while (j < arr2.length) { 21 newArr.push(arr2[j]); 22 j++; 23 } 24 25 return newArr; 26} 27

Find the intersection of two arrays.

Check if one array is a subsequence of the other.

Merge two sorted arrays.

Finding median values of 2 arrays.

I don't know

346. Moving Average from Data Stream

Problem Description

Intuition

Solution Implementation

Solution Approach

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Example Walkthrough

Time and Space Complexity

Common Pitfalls

1. Integer Division Instead of Float Division

2. Incorrectly Handling the Initial Window Fill

3. Forgetting to Update the Sum Before Overwriting

4. Not Handling Edge Case of Size 0

5. Using a Queue Instead of Circular Array

Recommended Readings