LeetCode 346 - Moving Average from Data Stream

The problem asks us to design a data structure that continuously receives integers from a stream and returns the average of the most recent values within a fixed-size sliding window. A sliding window means that we only care about the latest size elements.

leetcodeeasyarraydesignqueuedata-stream

LeetCode Problem 346

Difficulty: 🟢 Easy
Topics: Array, Design, Queue, Data Stream

Solution

Problem Understanding

The problem asks us to design a data structure that continuously receives integers from a stream and returns the average of the most recent values within a fixed-size sliding window.

A sliding window means that we only care about the latest size elements. As new values arrive, older values eventually fall out of the window once the capacity is exceeded.

For example, if the window size is 3 and the stream is:

1, 10, 3, 5

Then the moving averages are:

[1]                -> 1.0
[1, 10]            -> 5.5
[1, 10, 3]         -> 4.66667
[10, 3, 5]         -> 6.0

Notice that after inserting 5, the oldest value 1 is removed because the window can only contain three elements.

The input consists of repeated calls to the next(val) method. Each call inserts a new integer into the stream and returns the average of the current sliding window.

The constraints are relatively small:

  • The window size is at most 1000
  • At most 10^4 calls are made
  • Values may be negative

Although the constraints are not extremely large, the problem is clearly testing efficient stream processing and queue-based design. A naive implementation that recomputes the sum of the entire window every time would work, but it performs unnecessary repeated computation.

Several edge cases are important:

  • The window may not yet be full, so the divisor is the current number of elements rather than the maximum size.
  • Negative numbers must be handled correctly in the average.
  • A window size of 1 means the answer is always the latest value.
  • Large sequences of operations should avoid repeatedly summing the entire window.

Approaches

Brute Force Approach

The simplest solution is to store all values currently inside the sliding window in a list or queue. Whenever next(val) is called:

  1. Add the new value to the window.
  2. If the window exceeds the allowed size, remove the oldest value.
  3. Recompute the sum of all elements in the window.
  4. Divide by the number of elements currently stored.

This approach is correct because the average is always defined as:

sum(window) / len(window)

However, recomputing the sum every time is inefficient. If the window size is k, each call to next() requires O(k) time because we iterate through the entire window to calculate the sum.

Even though k <= 1000, this repeated work is unnecessary.

Optimal Approach

The key observation is that the window changes incrementally.

When a new value arrives:

  • One value is added
  • At most one old value is removed

Instead of recalculating the entire sum every time, we can maintain a running sum.

Suppose the current window sum is:

current_sum

When adding a new value:

current_sum += val

If the window becomes too large and we remove the oldest value:

current_sum -= removed_value

Now the average can be computed instantly:

current_sum / len(window)

This avoids repeatedly traversing the window and reduces each operation to constant time.

A queue is the ideal data structure because:

  • New values are inserted at the back
  • Oldest values are removed from the front
Approach Time Complexity Space Complexity Notes
Brute Force O(k) per operation O(k) Recomputes the entire sum every time
Optimal O(1) per operation O(k) Maintains a running sum with a queue

Here, k is the window size.

Algorithm Walkthrough

Optimal Sliding Window Algorithm

  1. Initialize an empty queue to store the elements currently inside the sliding window.
  2. Store the maximum allowed window size in a variable such as size.
  3. Maintain a running sum variable initialized to 0.
  4. When next(val) is called, append val to the queue because it becomes part of the current window.
  5. Add val to the running sum. This updates the total sum without recalculating everything.
  6. Check whether the queue size exceeds the allowed window size.
  • If it does, remove the oldest element from the front of the queue.
  • Subtract the removed value from the running sum.
  1. Compute the average using:
running_sum / current_window_size
  1. Return the computed floating-point average.

Why it works

The algorithm maintains an important invariant:

running_sum == sum(all elements currently in the queue)

Whenever a new value enters the window, it is added to both the queue and the running sum. Whenever an old value leaves the window, it is removed from both the queue and the running sum.

Because this invariant is always preserved, dividing the running sum by the number of elements in the queue always produces the correct moving average.

Python Solution

from collections import deque
from typing import Deque

class MovingAverage:

    def __init__(self, size: int):
        self.size = size
        self.window: Deque[int] = deque()
        self.current_sum = 0

    def next(self, val: int) -> float:
        self.window.append(val)
        self.current_sum += val

        if len(self.window) > self.size:
            removed_value = self.window.popleft()
            self.current_sum -= removed_value

        return self.current_sum / len(self.window)

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

The implementation uses Python's deque from the collections module because it provides efficient insertion and removal operations from both ends.

The constructor stores:

  • The maximum window size
  • The queue itself
  • The running sum

Inside next():

  • The new value is appended to the queue.
  • The running sum is updated immediately.
  • If the queue becomes too large, the oldest value is removed using popleft().
  • The removed value is subtracted from the running sum.
  • The average is returned using the current queue length.

The implementation directly follows the sliding window algorithm described earlier.

Go Solution

type MovingAverage struct {
	size       int
	window     []int
	currentSum int
}

func Constructor(size int) MovingAverage {
	return MovingAverage{
		size:       size,
		window:     []int{},
		currentSum: 0,
	}
}

func (this *MovingAverage) Next(val int) float64 {
	this.window = append(this.window, val)
	this.currentSum += val

	if len(this.window) > this.size {
		removedValue := this.window[0]
		this.currentSum -= removedValue
		this.window = this.window[1:]
	}

	return float64(this.currentSum) / float64(len(this.window))
}

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

The Go implementation uses a slice to simulate the queue.

Appending is done with:

append(this.window, val)

Removing the oldest element is done with slicing:

this.window = this.window[1:]

Go requires explicit conversion to float64 before division to avoid integer division.

Because the constraints are small, using slice reallocation here is completely acceptable.

Worked Examples

Example 1

Input:

size = 3
stream = [1, 10, 3, 5]
Step New Value Window Contents Running Sum Average
1 1 [1] 1 1.0
2 10 [1, 10] 11 5.5
3 3 [1, 10, 3] 14 4.66667
4 5 [10, 3, 5] 18 6.0

Detailed walkthrough:

After inserting 1:

window = [1]
sum = 1
average = 1 / 1 = 1.0

After inserting 10:

window = [1, 10]
sum = 11
average = 11 / 2 = 5.5

After inserting 3:

window = [1, 10, 3]
sum = 14
average = 14 / 3 = 4.66667

After inserting 5:

window temporarily = [1, 10, 3, 5]
sum temporarily = 19

The window exceeds size 3, so remove 1:

window = [10, 3, 5]
sum = 18
average = 18 / 3 = 6.0

Complexity Analysis

Measure Complexity Explanation
Time O(1) per operation Each insertion and removal happens once
Space O(k) The queue stores at most k elements

The algorithm is efficient because every call to next() performs only constant-time operations:

  • Append to queue
  • Possibly remove one element
  • Update the running sum
  • Compute the average

No traversal of the window is required after initialization.

The space complexity is proportional to the window size because we only store the active sliding window.

Test Cases

# Example from problem statement
obj = MovingAverage(3)
assert obj.next(1) == 1.0          # single element
assert obj.next(10) == 5.5         # average of two elements
assert abs(obj.next(3) - 4.6666666667) < 1e-6  # full window
assert obj.next(5) == 6.0          # oldest element removed

# Window size of 1
obj = MovingAverage(1)
assert obj.next(5) == 5.0          # only current value matters
assert obj.next(10) == 10.0        # previous value removed immediately

# Negative values
obj = MovingAverage(2)
assert obj.next(-1) == -1.0
assert obj.next(-5) == -3.0
assert obj.next(3) == -1.0         # window becomes [-5, 3]

# Mixed positive and negative
obj = MovingAverage(3)
assert obj.next(5) == 5.0
assert obj.next(-5) == 0.0
assert obj.next(10) == 10 / 3
assert obj.next(0) == 5 / 3

# Large window not yet full
obj = MovingAverage(5)
assert obj.next(1) == 1.0
assert obj.next(2) == 1.5
assert obj.next(3) == 2.0

# Repeated identical values
obj = MovingAverage(4)
assert obj.next(7) == 7.0
assert obj.next(7) == 7.0
assert obj.next(7) == 7.0
assert obj.next(7) == 7.0
assert obj.next(7) == 7.0
Test Why
Problem statement example Validates normal sliding window behavior
Window size = 1 Ensures immediate eviction works
Negative values Confirms sums and averages handle negatives correctly
Mixed positive and negative Verifies arithmetic correctness
Window not yet full Ensures divisor uses current size
Repeated identical values Checks stable running sum behavior

Edge Cases

Window Size of One

When the window size is 1, every new value immediately replaces the previous one. A buggy implementation might accidentally keep older values or divide by the wrong count.

This implementation handles the case naturally because the queue automatically removes the oldest value whenever the size exceeds 1.

Window Not Yet Full

At the beginning of the stream, the number of inserted elements may be smaller than the maximum window size.

For example:

size = 5
stream = [1, 2]

The average should be:

(1 + 2) / 2

not divided by 5.

The implementation correctly divides by len(window) rather than the fixed window size.

Negative Numbers

Negative values can expose bugs in running-sum logic, especially if removal is handled incorrectly.

For example:

window = [-5, 3]
sum = -2
average = -1

The implementation always updates the running sum consistently during both insertion and removal, so negative numbers work correctly without any special handling.

Continuous Stream Growth

A naive implementation might accidentally store every value ever seen, causing memory growth over time.

This implementation only stores at most size elements in the queue. Old elements are removed immediately once they leave the sliding window, guaranteeing bounded memory usage.