Moving Average from Data Stream Leetcode Solution

Difficulty Level Easy
Frequently asked in Amazon Apple Bloomberg Facebook Microsoft PayPal Spotify Uber
Array Design QueueViews 26

Problem Statement

The Moving Average from Data Stream LeetCode Solution – “Moving Average from Data Stream” states that given a stream of integers and a window size k. We need to calculate the moving average of all the integers in the sliding window. If the number of elements in the stream is less than k, take all the elements.

We need to implement the Moving Average class:

  • MovingAverage(int size): Initializes the size of the window as size.
  • double next(int val): Returns the moving average of the last size values of the stream

Example:

Moving Average from Data Stream Leetcode SolutionPin

 

 

Input: ["MovingAverage","next","next","next","next"]
[[3],[1],[10],[3],[5]]
Output: [null, 1.0, 5.5, 4.66667, 6.0]

Explanation:

  • Initializes the MovingAverage Class with window size 3.
  • 1 appears in the stream as the first element. Average  = 1/1 = 1 [total elements is still less than  3].
  • 10 appears in the stream as the second element. Average = (1+10)/2 = 5.5 [total elements is still less than 3].
  • 3 appears in the stream as the third element. Average = (1+10+3)/3 = 4.66667 [total elements is 3].
  • 5 appears in the stream as the fourth element. We need to pick the last 3 elements that appeared in the stream. Average = (10+3+5) = 6.0 .

Approach

Idea:

  1. At each step, we need only the last k elements that appeared in the stream of integers, where k = window size.
  2. We will maintain a deque (double-ended queue) of maximum size k, which will help to insert and pop out(when the window size is strictly greater than k) elements efficiently.
  3. Maintain the sum of those elements which are present in the deque using a global sum variable.
  4. Whenever we have a new element from a data stream insert the element in the back of the deque and increment the sum with the current value.
  5. Also, take care that when the size of the deque exceeds the desired window size, we need to pop out the element present at the front of the deque and decrement the value of the sum variable since we need only the last k elements from the data stream.
  6. Compute the average as the sum of elements/size of the double-ended queue at the current state.

Code

Moving Average from Data Stream Leetcode C++ Solution:

class MovingAverage {
public:
    int k;
    double sum = 0;
    deque<int> elements;
    MovingAverage(int size) {
        k = size;
    }    
    double next(int val) {
        elements.push_back(val);
        sum += val;
        if(elements.size()>k){
            sum -= elements.front();
            elements.pop_front();
        }
        int sz = min((int)elements.size(),k);
        return sum/sz;
    }
};

Moving Average from Data Stream Leetcode Java Solution:

class MovingAverage {
    int k,sum;
    Deque q = new ArrayDeque<Integer>();
    public MovingAverage(int size) {
        this.k = size;
        this.sum = 0;
    }
    public double next(int val) {
        q.add(val);
        sum += val;
        int curr_size = q.size();
        if(curr_size>k){
            curr_size = curr_size - 1;
            sum = sum - (int)q.poll();
        }
        return (sum*1.0)/curr_size;
    }
}

Complexity Analysis for Moving Average from Data Stream Leetcode Solution

Time Complexity

The time complexity of the above code is O(1) since inserting and popping out elements in a double-ended queue takes constant time.

Space Complexity

The space complexity of the above code is O(k), where k = window size. At any time, we had maintained a double-ended queue of size at most k.

Translate »