Java O(1) time solution.


  • 36
    S

    The idea is to keep the sum so far and update the sum just by replacing the oldest number with the new entry.

    public class MovingAverage {
        private int [] window;
        private int n, insert;
        private long sum;
        
        /** Initialize your data structure here. */
        public MovingAverage(int size) {
            window = new int[size];
            insert = 0;
            sum = 0;
        }
        
        public double next(int val) {
            if (n < window.length)  n++;
            sum -= window[insert];
            sum += val;
            window[insert] = val;
            insert = (insert + 1) % window.length;
            
            return (double)sum / n;
        }
    }

  • 14
        Queue<Integer> q;
        double sum = 0;
        int size;
    
        public MovingAverage(int s) {
            q = new LinkedList();
            size = s;
        }
        
        public double next(int val) {
            if(q.size() == size){
                sum = sum - q.poll();
            }
            q.offer(val);
            sum += val;
            return sum/q.size();
        }

  • 0
    M

    @hot13399
    To prevent overflow,

    double sum = 0;

  • 0
    V

    Perfect solution.


  • 0

    @hot13399 very nifty way to simulate a circular buffer through a bounded queue!


  • 0
    H

    Will result in Divide By Zero error for input [10, -10]
    You need to validate sum to zero before dividing by n, in return statement.


Log in to reply
 

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