Java easy to understand solution


  • 16
    B

    Essentially, we just need to keep track of the sum of the current window as we go. This prevents an O(n) traversal over the Queue as we add new numbers to get the new average. If we need to evict then we just subtract that number off of our sum and divide by the size.

    public class MovingAverage {
    private double previousSum = 0.0;
    private int maxSize;
    private Queue<Integer> currentWindow;
    
    public MovingAverage(int size) {
        currentWindow = new LinkedList<Integer>();
        maxSize = size;
    }
    
    public double next(int val) {
        if (currentWindow.size() == maxSize)
        {
            previousSum -= currentWindow.remove();
        }
        
        previousSum += val;
        currentWindow.add(val);
        return previousSum / currentWindow.size();
    }}

  • 0
    G

    Can you share the overall running time for the test cases? Mine is 200+ms, is it too slow?


  • 0
    B

    My submissions range from 160 - 190. I assume they just have some very large test cases and I'm not sure you can really get much faster than this. The removal from the Queue is constant time, as is the addition. So the next function is O(1). It will be interesting to see the distribution when enough submissions are made, though. :)


  • 0
    G

    Yeah, definitely great to look at the distribution : )


  • 0
    F

    @GuaGua1991 Mine is 137ms. Beats 98.12%. But each time the runtime is different.


  • 0
    C

    Hey,guys! Here is my idea.

    public class MovingAverage {
        List<Integer> list;
        int size;
        public MovingAverage(int size) {
            this.size = size  ;
            list = new LinkedList<>();        
        }
        
        public double next(int val) {        
            list.add(val);
            if(list.size() > size){
                list.remove(0);
            }
            double sum = 0;
            int i;
            for(i=0; i<list.size(); i++){
                sum += list.get(i);
            }
            return sum/i;
        }
    }

  • 0
    C

    @chanjjeaseo 700+ms It`s slow.But easy to understand.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.