Leetcode 346. Moving Average from Data Stream

Problem Explanation:

Given a stream of integers and a window size, your task is to calculate the moving average of all integers in the sliding window.

For instance, if we initiate a MovingAverage class with window size 3. And add in values {1, 10, 3, and 5}, the expected output would be as follows:

• m.next(1) = 1
• m.next(10) = (1 + 10) / 2
• m.next(3) = (1 + 10 + 3) / 3
• m.next(5) = (10 + 3 + 5) / 3

As explained, the average for the next function is always the average of the last size numbers in the series.

Approach:

The problem can be addressed by using a queue. We insert elements into the queue in the next(val) function. The size of our queue is limited though, i.e., the size of the window. If the queue size is full, we take the first element out of the queue before we add the current element into the queue. We then calculate the average of the elements in the queue and return the calculated average.

Example:

Let's say, MovingAverage m = new MovingAverage(2), so we limit the queue size to 2. And the integers stream is {1, 10, 3, and 5}.

• m.next(1) = 1/1 = 1, insert 1 into queue, queue: {1}.
• m.next(10) = (1 + 10) / 2 = 5.5, insert 10 into queue, queue: {1, 10}.
• m.next(3) = (10 + 3) / 2 = 6.5, since queue size is 2, we need to remove the first element 1 before adding 3 into the queue, now the queue: {10, 3}.
• m.next(5) = (3 + 5) / 2 = 4, remove 10 before adding 5 into the queue, now the queue: {3, 5}.

Let's script solutions for this problem in different programming languages.

Python Solution:

1
2python
3from collections import deque
4class MovingAverage:
5    def __init__(self, size):
6        # Initialize data structure
7        self.size = size
8        self.queue = deque()
9        self.window_sum = 0.0
10
11    def next(self, val):
12        # Add the new integer in the stream into queue
13        if len(self.queue) == self.size:
14            # If the queue is full, subtract the oldest value from the sum
15            self.window_sum -= self.queue.popleft()
16        self.queue.append(val)
17        self.window_sum += val
18        # Caculate the average
19        return self.window_sum / len(self.queue)

JavaScript Solution:

1
2javascript
3class MovingAverage {
4    constructor(size) {
5        this.queue = [] 
6        this.size = size 
7        this.sum = 0 
8    }
9    
10    next(val) {
11        //If the queue is full, subtract the oldest value from the sum
12        if (this.queue.length == this.size){ 
13            this.sum -= this.queue.shift()
14        }  
15        this.queue.push(val)
16        this.sum += val
17        //Caculate the average
18        return this.sum / this.queue.length; 
19    }
20}

Java Solution:

1
2java
3import java.util.LinkedList;
4import java.util.Queue;
5
6class MovingAverage {
7    private Queue<Integer> queue;
8    private double sum = 0.0;
9    private int size;
10    
11    public MovingAverage(int size) {
12        queue = new LinkedList<>();
13        this.size = size;
14    }
15    
16    public double next(int val) {
17        if (queue.size() == size){
18            sum -= queue.poll();
19        } 
20        queue.add(val);
21        sum += val;
22        return sum / queue.size();
23    }
24}

C# Solution:

1
2csharp
3public class MovingAverage {
4    private Queue<int> queue;
5    private double sum = 0.0;
6    private int size;
7    
8    public MovingAverage(int size) {
9        this.size = size;
10        queue = new Queue<int>(size);
11    }
12    
13    public double next(int val) {
14        if (queue.Count == size){
15            sum -= queue.Dequeue();
16        } 
17        queue.Enqueue(val);
18        sum += val;
19        return sum / queue.Count;
20    }
21}

C++ Solution:

1
2cpp
3#include <queue>
4using namespace std;
5
6class MovingAverage {
7    queue<int> q;
8    double sum = 0;
9    int size;
10public:
11    MovingAverage(int size) {
12        this->size = size;
13    }
14    
15    double next(int val) {
16        if (q.size() == size) {
17            sum -= q.front(); q.pop();
18        }
19        sum += val; q.push(val);
20        return sum / q.size();
21    }
22};

Explanation on each solution:

Python Solution:

In Python, we can use the built-in deque from the collections module to simulate a queue easily. The deque is a double-ended-queue where elements can be added and removed from both ends. In this case, we are using it as a regular queue where new elements are appended at the right end and old values are popped out from the left end.

We initialize the required variables: size, queue, and window_sum in the constructor. While window_sum is the sum of the stream, we initialize it with 0.0 to ensure that any division operation results in a float.

The next(val) function handles the incoming stream. When the stream is at the max size, we subtract the oldest value (the leftmost value in the queue) from window_sum. This maintains the sum for the stream in the sliding window. We then append the new integer at the end of the queue and add it to window_sum. Lastly, we return the current average which is the sum of elements divided by the number of elements (length of the queue).

JavaScript Solution:

In JavaScript, an array can be used as a queue. We push elements at the end and shift elements from the beginning to maintain the queue's FIFO property.

The constructor initializes the empty queue, the size, and the sum. Similar to the Python solution, the next(val) function will subtract the oldest value from the sum if the queue reaches its max size, push the new integer to the end of the queue and add it to the sum. The average is then calculated and returned.

Java Solution:

Java’s Queue interface can be used to implement a queue. We use a LinkedList to instantiate the Queue in the class constructor.

Again, similar to the other solutions, in the next(val) function, we perform the same operations: poll (which is equivalent to dequeue, which gets and removes the head of the queue) if the queue is full, add the new value to the queue, and calculate then return the average.

C# Solution:

In C#, the Queue class under System.Collections namespace is used. The approach is the same as in the previous solutions with Dequeue method used to remove the oldest value from the queue if the queue is full and Enqueue method used to add the new value into the queue.

C++ Solution:

C++ has a queue utility in its Standard Template Library (STL). It works in the same way as in other languages. However, the method to add an item in the queue is push and to remove an item is pop. The front of the queue (the oldest item) can be accessed with the front method. The rest of the flow remains the same as explained before.