346. Moving Average from Data Stream
Moving Average from Data Stream (LeetCode 346) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Fixed Size (Subarray Calculation) subpattern.
How to solve Moving Average from Data Stream
Moving Average from Data Stream is a Fixed Size Sliding Window problem, part of Sliding Window. Learn fixed-size sliding window for subarray calculations like maximum average, moving average, and k-size subarray problems.
Work towards the solution in these steps:
- Consider using a data structure that can efficiently represent the last 'size' elements received to compute the moving average.
- Think about how a sliding window approach can help maintain the current subset of elements needed for the average calculation as new elements arrive.
- Instead of recalculating the sum of the entire window each time, explore how you can update the sum incrementally when adding a new element and removing the oldest one.
The reference solution runs in O(N) time and O(K) space.
The Moving Average from Data Stream solution and editorial walks through the full approach with reference code.
Problem statement
You are given a class MovingAverage that receives a stream of integers. Initialize the object with an integer size, representing the size of a moving window. Implement the next(val) method, which accepts an integer val and returns the moving average of the last size values in the stream (including the current val). If the number of elements seen so far is less than size, compute the average of all elements received so far.
Return the moving average as a floating point number after each call to next(val).
Examples
Example 1
Input: {"constructor_args": [3], "operations": ["next", "next", "next"], "arguments": [[1], [10], [3]]}
Output: [1.0, 5.5, 4.666666666666667]
Explanation: With a window size of 3, the averages after receiving 1, 10, and 3 are 1.0, 5.5, and 4.666666666666667, respectively.
Example 2
Input: {"constructor_args": [2], "operations": ["next", "next", "next"], "arguments": [[5], [-1], [7]]}
Output: [5.0, 2.0, 3.0]
Explanation: With a window size of 2, the averages are 5.0 after receiving 5, 2.0 for 5 and -1, and 3.0 for the last two values -1 and 7.
Topics and companies
Topics: Array, Design, Queue, Data Stream.
Reported in interviews at Google, Apple, Spotify, Indeed, Amazon.
How to practise Moving Average from Data Stream on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N) time and O(K) space.
Open Moving Average from Data Stream in the code editor, or read the Moving Average from Data Stream editorial for a worked solution with its approach and complexity analysis.
Where Moving Average from Data Stream sits in the DSA pattern sheet
Problems related to Moving Average from Data Stream
Other problems that use the same Fixed Size (Subarray Calculation) and Sliding Window techniques:
- Calculate Compressed Mean — Easy, same subpattern
- Find the Power of K-Size Subarrays I — Medium, same subpattern
- Find X-Sum of All K-Long Subarrays I — Easy, same subpattern
- Maximum Average Subarray I — Easy, same subpattern
- Contains Duplicate II — Easy, same pattern
- Continuous Subarrays — Medium, same pattern
Moving Average from Data Stream FAQ
What is the LeetCode number of Moving Average from Data Stream?
Moving Average from Data Stream is LeetCode problem 346, rated Easy.
What pattern is used to solve Moving Average from Data Stream?
Moving Average from Data Stream is a Fixed Size Sliding Window problem. It belongs to the Sliding Window pattern, in the Fixed Size (Subarray Calculation) subpattern.
What is the time complexity of Moving Average from Data Stream?
The reference solution runs in O(N) time and O(K) space.
Which companies ask Moving Average from Data Stream?
Moving Average from Data Stream has been reported in interviews at Google, Apple, Spotify, Indeed, Amazon.