Simple Python solution based on Circular Array - real O(1) time next()

  • 11
    class MovingAverage(object):
        def __init__(self, size):
            self.vect, self.sums, self.idx, self.size = [0] * size, 0, 0, size
        def next(self, val):
            self.idx += 1
            self.sums -= self.vect[self.idx % self.size]
            self.vect[self.idx % self.size] = val
            self.sums += val
            return self.sums / float(min(self.idx, self.size))

    My solution requires real O(1) time for next() operation as it is not needed to compute the sum every time. We just subtract the element that is exiting from the sliding window, and we're done. We need also to substitute that element with the new one.

  • 0

    @agave Can you explain the brain working on how you reached this solution?

  • 0

    @kaddu what is it that you don't understand?

  • 0

    The circular array idea is very nice, thank you! I just have a minor suggestion, not sure if you like it.

    You can initiate your self.sum to be float (0.0), so you wouldn't need to convert the integer to float explicitly. I also did some local testing, without explicitly convert int to float the speed of adding two numbers is two times faster.


    a = 1
    a += float(2)
    # VS
    a = 1.0
    a += 2

  • 0

    It looks confusing when you initialize all the variables on a single line. Please consider breaking it up.

Log in to reply

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