We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Moving Average from Data Stream

Number: 346

Difficulty: Easy

Paid? Yes

Companies: Meta, Google, Amazon, Spotify, Microsoft, Citadel, Bloomberg, ZScaler

Problem Description

Design a class to calculate the moving average of a stream of integers. The class is initialized with a fixed window size, and each new number from the stream is added to this window. If the window exceeds its size, the oldest number is removed. The moving average is then the sum of the numbers in the window divided by the number of elements in the window.

Key Insights

  • Use a queue (or circular buffer) to keep track of the current window elements.
  • Maintain a running sum to quickly update the window's total when a new element comes in.
  • When the window is full, subtract the value of the element that falls out as a new one is added.
  • Each call to next() is executed in constant time, O(1).

Space and Time Complexity

Time Complexity: O(1) per call to next()
Space Complexity: O(window size)

Solution

The solution leverages a queue data structure to store the elements of the sliding window. A running sum variable is maintained for efficient calculation of the moving average. When a new integer is added:

  • If the size of the queue is equal to the maximum window size, remove the oldest element and subtract its value from the running sum.
  • Add the new element to both the queue and the running sum.
  • Compute and return the moving average as the running sum divided by the number of elements in the queue. This approach ensures that each update is done in constant time without having to sum all elements in the window repeatedly.

Code Solutions

# Python solution for Moving Average from Data Stream

from collections import deque  # Import deque for efficient queue operations

class MovingAverage:
    def __init__(self, size):
        # Initialize with the maximum window size
        self.size = size                # Maximum number of elements in the window
        self.queue = deque()            # Queue to store current window values
        self.current_sum = 0            # Running sum of the current window

    def next(self, val):
        # Add new value to the window
        if len(self.queue) == self.size:
            # If the window is full, remove the oldest element and update the sum
            removed_val = self.queue.popleft()  # Remove the front element
            self.current_sum -= removed_val     # Subtract its value from the running sum
        # Append the new value to the queue and update the sum
        self.queue.append(val)
        self.current_sum += val
        
        # Calculate and return the moving average by dividing the running sum by the current window size
        return self.current_sum / len(self.queue)
← Back to All Questions