Java and Python, fixed size array


  • 0
    S

    Fixed size array is enough for this problem.

    Java:

    public class MovingAverage {
        int[] window;
        int index = 0;
        /** Initialize your data structure here. */
        public MovingAverage(int size) {
            this.window = new int[size];
        }
        
        public double next(int val) {
            this.window[index] = val;
            index = (index+1)%this.window.length;
            double ans = 0.0;
            for (int i:window) {
                ans += i;
            }
            return ans/this.window.length;
        }
    }
    

    Python:

    class MovingAverage(object):
    
        def __init__(self, size):
            """
            Initialize your data structure here.
            :type size: int
            """
            self.size = size;
            self.window = [0]*size;
            self.index = 0;
        def next(self, val):
            """
            :type val: int
            :rtype: float
            """
            self.window[self.index] = val
            self.index = (self.index+1)%self.size
            return float(sum(self.window))/self.size

  • 0
    M

    When the first element is stored and window.length is (say) 3. You are calculating the average using sum/window.length. It should actually be sum/1.

    So the solution is wrong.


  • 0
    J

    When your window is not yet filled you should return its current sum divided by current number of elements, instead of window size. Also it's a bit inefficient to iterate your window array every time, which would make next() 's time complexity O(k) instead of O(1).

    You can still use the circular buffer idea by maintaining current sum and count of elements.

    public class MovingAverage{
    int[] window;
    int index = 0;
    int sum = 0;
    int count = 0;

    public MovingAverage(int size){
        this.window = new int[size];
    }
    
    public double next(int val) {
        if(index < window.length - 1){
            window[index++] = val;
            sum += val;
            count ++;
        } else {
            index = (index + 1) % window.length;
            sum -= window[index];
            window[index] = val;
            sum += val;
        }
        
        return (double) sum / count;
    }
    

    }


  • 0

    It's not wrong... It's suboptimal. You get the correct result but you're doing unnecessary computation.


Log in to reply
 

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