Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

Leetcode 346. Moving Average from Data Stream

Asked at:

Google

Meta

DESCRIPTION

Design a data structure MovingAverage that efficiently calculates the moving average of the last k numbers from a continuous stream. Each time a new value arrives via next(val), the structure should return the average of the most recent k values (or fewer if less than k values have been received). For example, with k=3, after receiving values [1, 10, 3, 5], calling next(5) should return 6.0 (average of 3, 5, 5).

Input:

MovingAverage(3)
next(1) → 1.0
next(10) → 5.5
next(3) → 4.666...
next(5) → 6.0

Output:

1.0, 5.5, 4.666..., 6.0

Explanation: Window size is 3. First call has only [1], second has [1,10], third has [1,10,3], fourth has [10,3,5] (oldest value 1 is removed).

Constraints:

Window size k is fixed at initialization and 1 ≤ k ≤ 10^4
At most 10^4 calls to next(val) will be made
Values are in range [-10^5, 10^5]
Must achieve O(1) time complexity for next() operation
Must use O(k) space complexity

Understanding the Problem

The core challenge is maintaining a sliding window of exactly k elements while computing averages in constant time. A naive approach of storing all values and recalculating the sum each time would be O(k) per operation. The key insight is to use a circular buffer (queue) to track the window and maintain a running sum that updates incrementally: add the new value, subtract the evicted value (if window is full), then divide by the current window size.

Building Intuition

The naive approach recalculates the sum of all k values on every next() call, resulting in O(k) time complexity. The optimized approach maintains a running sum: when a new value arrives, add it to the sum; when the window exceeds size k, subtract the oldest value. This reduces each operation to O(1). For example, with window [10, 3, 5] and sum 18, adding 7 gives sum 25, then removing 10 gives sum 15 for new window [3, 5, 7].

Moving averages are fundamental in real-time analytics, financial trading systems (stock price smoothing), and IoT sensor monitoring (temperature/pressure trends). Efficient constant-time updates enable processing millions of data points per second without performance degradation. This pattern of maintaining incremental state (running sum) instead of recomputing from scratch applies broadly to streaming algorithms.

Common Pitfalls

Pitfall: Recalculating sum from all window elements each time → Fix: Maintain a running sum and update it incrementally

Pitfall: Using a list and removing from the front (O(k) operation) → Fix: Use a circular buffer or deque for O(1) removal

Pitfall: Integer overflow with large sums → Fix: Use floating-point arithmetic or handle overflow explicitly

Pitfall: Forgetting to handle the case when fewer than k values exist → Fix: Track actual window size separately

Implementation

Circular Buffer Implementation

Implement the sliding window using a circular buffer (deque) to store the last k values. The deque allows O(1) insertion at the back and removal from the front. Track the running sum of all values in the window and the current window size. When a new value arrives: (1) add it to the deque and sum, (2) if the deque exceeds size k, remove the oldest value from both deque and sum, (3) return sum / size. For example, with k=3 and window [1, 10, 3] (sum=14), adding 5 gives [10, 3, 5] (sum=18) and average 6.0.

Solution

from collections import deque
class MovingAverage:
    def __init__(self, size: int):
        self.k = size
        self.window = deque()
        self.sum = 0
    
    def next(self, val: int) -> float:
        self.window.append(val)
        self.sum += val
        
        if len(self.window) > self.k:
            removed = self.window.popleft()
            self.sum -= removed
        
        return self.sum / len(self.window)

Optimized Array-Based Circular Buffer

Replace the deque with a fixed-size array and two pointers (head and tail) to implement a true circular buffer, eliminating dynamic memory allocation overhead. Use modulo arithmetic (index % k) to wrap around the array. Track the running sum and count as before. When the buffer is full, overwrite the oldest element at head position, subtract its value from the sum, then advance head. This approach uses exactly O(k) space with better cache locality. For example, with k=3 and array [1, 10, 3] at indices [0, 1, 2], adding 5 overwrites index 0, giving [5, 10, 3] with head=1.

Solution

class MovingAverageOptimized:
    def __init__(self, size: int):
        self.k = size
        self.buffer = [0] * size
        self.head = 0
        self.count = 0
        self.sum = 0
    
    def next(self, val: int) -> float:
        if self.count < self.k:
            self.buffer[self.count] = val
            self.sum += val
            self.count += 1
        else:
            self.sum -= self.buffer[self.head]
            self.buffer[self.head] = val
            self.sum += val
            self.head = (self.head + 1) % self.k
        
        return self.sum / self.count

Complete Integration

Combine the circular buffer logic from Section 2 with initialization and query methods into a complete MovingAverage class. The constructor initializes the fixed-size array, pointers, sum, and count. The next(val) method implements the full update logic: add the new value, handle window overflow by subtracting the evicted element, update pointers, and return the average. Include helper methods for clarity, such as is_full() to check if the window has reached size k. This unified structure demonstrates how the circular buffer and running sum work together to achieve O(1) time and O(k) space.

Solution

class MovingAverage:
    def __init__(self, size: int):
        self.k = size
        self.buffer = [0] * size
        self.head = 0
        self.count = 0
        self.sum = 0
    
    def next(self, val: int) -> float:
        if self.count < self.k:
            self.buffer[self.count] = val
            self.sum += val
            self.count += 1
        else:
            self.sum -= self.buffer[self.head]
            self.buffer[self.head] = val
            self.sum += val
            self.head = (self.head + 1) % self.k
        return self.sum / self.count
    
    def is_full(self) -> bool:
        return self.count == self.k

What We've Learned

Pattern: Use a circular buffer + running sum to maintain sliding windows in O(1) time per operation
Use Case: Real-time analytics, financial indicators (SMA), sensor data smoothing, and any streaming aggregation
Optimization: Fixed-size arrays with modulo indexing outperform dynamic deques for cache efficiency
Generalization: This incremental update pattern extends to other sliding window aggregates (min/max with deque, median with heaps)

Problems to Practice

Overview

Lesson

Sliding Window

This lesson directly teaches the fixed-length sliding window pattern, which is the exact technique needed for the Moving Average problem. It covers maintaining a window of size k and efficiently updating calculations as elements enter and leave the window.

Learn

Maximum Sum of Subarrays of Size K

easy

Sliding Window

This problem uses the identical fixed-size sliding window pattern as Moving Average. Instead of calculating an average, it finds the maximum sum, but the core technique of maintaining a window of k elements with O(1) updates is exactly the same.

Practice

Max Sum of Distinct Subarrays Length k

medium

Sliding Window

This problem builds on the fixed-size sliding window pattern by adding the constraint of tracking distinct elements. It reinforces the same O(k) space and O(1) update operations while introducing additional state management within the sliding window.

Practice

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Late September, 2025

Meta

Senior

Early September, 2025

Meta

Senior

Early August, 2025

Meta

Senior

Variant: entire array available at once, sliding window

Get Premium to View All 9 Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 346. Moving Average from Data Stream

DESCRIPTION

Understanding the Problem

Building Intuition

Common Pitfalls

Implementation

Circular Buffer Implementation

Optimized Array-Based Circular Buffer

Complete Integration

What We've Learned

Problems to Practice

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact