LeetCode 346: Moving Average from Data Stream Solution in Python – A Step-by-Step Guide

What Is LeetCode 346: Moving Average from Data Stream?

In LeetCode 346: Moving Average from Data Stream, you’re tasked with implementing a MovingAverage class that maintains a fixed-size window of integers and computes their average each time a new value is added. For example, with a window size of 3 and values [1, 10, 3, 5], the averages are [1.0, 5.5, 4.67, 6.0]. This problem tests your ability to manage a sliding window efficiently, connecting to concepts in LeetCode 239: Sliding Window Maximum.

Problem Statement

• Input:
• __init__(size): Initialize with window size.
• next(val): Add value val, return moving average of last size values.
• Output:
• next() returns a float—the average of the current window.
• Rules:
• Window size is fixed.
• Average is computed over the last size values (or fewer if not full).
• Return floating-point average.

Constraints

• 1 <= size <= 1000
• -10⁵ <= val <= 10⁵
• At most 10⁴ calls to next().

Examples

• Input: ["MovingAverage", "next", "next", "next", "next"], [[3], [1], [10], [3], [5]]
• Output: [null, 1.0, 5.5, 4.66667, 6.0]
• Init(size=3), [1], [1,10], [1,10,3], [10,3,5]
• Input: ["MovingAverage", "next", "next"], [[2], [1], [2]]
• Output: [null, 1.0, 1.5]
• Init(size=2), [1], [1,2]
• Input: ["MovingAverage", "next"], [[1], [5]]
• Output: [null, 5.0]

Understanding the Problem: Tracking the Average

To solve LeetCode 346: Moving Average from Data Stream in Python, we need to design a class that maintains a window of the last size integers and computes their average with each new value, efficiently handling additions and removals. A naive approach—recomputing the sum each time—works but is slow. We’ll use:

• Best Solution (Queue-Based): O(1) time per call, O(size) space—fast and optimal.
• Alternative Solution (List-Based): O(n) time per call, O(size) space—simple but less efficient.

Let’s start with the queue-based solution, explained in a beginner-friendly way.

Best Solution: Queue-Based Approach

Why This Is the Best Solution

The queue-based approach is the top choice for LeetCode 346 because it’s efficient—O(1) amortized time per next() call, O(size) space—and perfectly suited for a sliding window. It uses a deque (double-ended queue) to add new values and remove old ones from the front, maintaining a running sum for instant averages. It’s like a conveyor belt keeping just the right amount of data—smart and quick!

How It Works

Think of this as a number conveyor:

• Step 1: Initialize:
• Deque to store up to size values.
• Track running sum and window size.
• Step 2: Add Value (next):
• If full (len == size), remove oldest (front), subtract from sum.
• Add new value (back), update sum.
• Step 3: Compute Average:
• Return sum / current length.
• Step 4: Why It Works:
• Deque ensures O(1) add/remove.
• Running sum avoids recomputation.

It’s like sliding a window over the stream with ease!

Step-by-Step Example

Example: size = 3, calls: [1, 10, 3, 5]

• Init: deque = [], sum = 0, size = 3
• next(1): deque = [1], sum = 1, avg = 1.0
• next(10): deque = [1, 10], sum = 11, avg = 11/2 = 5.5
• next(3): deque = [1, 10, 3], sum = 14, avg = 14/3 ≈ 4.67
• next(5):
• Full: pop 1, sum = 14-1 = 13
• Add 5: deque = [10, 3, 5], sum = 13+5 = 18, avg = 18/3 = 6.0
• Result: [1.0, 5.5, 4.67, 6.0]

Code with Detailed Line-by-Line Explanation

Copy codefrom collections import deque

class MovingAverage:
    def __init__(self, size: int):
        self.queue = deque()
        self.size = size
        self.sum = 0

    def next(self, val: int) -> float:
        # If full, remove oldest value
        if len(self.queue) == self.size:
            self.sum -= self.queue.popleft()

        # Add new value
        self.queue.append(val)
        self.sum += val

        # Return average
        return self.sum / len(self.queue)

• Lines 5-7: Init deque, size, and running sum.
• Lines 10-17: next():
• If full, pop left (oldest), subtract from sum.
• Append new value, add to sum.
• Return sum divided by current length.
• Time Complexity: O(1) amortized—deque ops are O(1).
• Space Complexity: O(size)—queue stores up to size elements.

This is like a conveyor-belt calculator—fast and sleek!

Alternative Solution: List-Based Approach

Why an Alternative Approach?

The list-based approach—O(n) time per call, O(size) space—uses a simple list to store values, recomputing the sum each time by shifting elements. It’s the easiest way to grasp the concept but inefficient due to shifting and sum recalculation. It’s like manually counting items each time—clear but slow!

How It Works

Shift and sum:

• Step 1: Init list with size limit.
• Step 2: Add value:
• Shift left (remove oldest), append new value.
• Step 3: Compute average from list sum.

Step-by-Step Example

Example: size = 2, calls: [1, 2, 3]

• Init: list = [], size = 2
• next(1): list = [1], avg = 1.0
• next(2): list = [1, 2], avg = 1.5
• next(3): Shift [2, 3], avg = 2.5
• Result: [1.0, 1.5, 2.5]

Code for List-Based Approach

Copy codeclass MovingAverage:
    def __init__(self, size: int):
        self.list = []
        self.size = size

    def next(self, val: int) -> float:
        if len(self.list) == self.size:
            self.list.pop(0)  # Remove oldest
        self.list.append(val)
        return sum(self.list) / len(self.list)

• Time Complexity: O(n) per call—list shift and sum are O(n).
• Space Complexity: O(size)—list size.

It’s a list-shifting counter—vivid but heavy!

Comparing the Two Solutions

• Queue-Based (Best):
• Pros: O(1) amortized time, O(size) space, fast and scalable.
• Cons: Queue logic less obvious.
• List-Based (Alternative):
• Pros: O(n) time per call, O(size) space, straightforward.
• Cons: Slow due to shifting and summing.

Queue-based wins for efficiency.

Additional Examples and Edge Cases

• size=1, [1,2]: [1.0, 2.0].
• size=3, [1]: [1.0].
• size=2, [5,5,5]: [5.0, 5.0, 5.0].

Both handle these, but queue-based is faster.

Complexity Breakdown

• Queue-Based: Time O(1) amortized, Space O(size).
• List-Based: Time O(n) per call, Space O(size).

Queue-based is the clear choice.

Key Takeaways

• Queue-Based: Slide smoothly—efficient!
• List-Based: Shift and sum—simple!
• Python: Deques and lists shine—see [Python Basics](/python/basics).
• Averages: Queues beat brute force.

Final Thoughts: Smooth the Stream

LeetCode 346: Moving Average from Data Stream in Python is a data structure design gem. The queue-based solution offers speed and elegance, while the list-based approach provides a tangible baseline. Want more streaming challenges? Try LeetCode 239: Sliding Window Maximum or LeetCode 295: Find Median from Data Stream. Ready to average? Head to Solve LeetCode 346 on LeetCode (premium) and smooth that stream today!