# O(n) solution (using simpler explanation than convex hull)

• I simply calculate the prefix sums while traversing the array. Here's the logic:

1. Start with the range being from i,j = [0,K-1]. Then iterate over remaining elements.
2. For every next element, j, we add, we have a choice - we can use the full range [i,j] or discard the range [i:j-k] and keep [j-k+1:j] (i.e keep the latest K elements). Choose the range with the higher average (use prefix sum to do this in O(1)).
3. Keep track of the max average at every step
4. Return the max avg at the end
Code:
``````class Solution(object):
def findMaxAverage(self, nums, k):
prefix = [0]
for i in range(k):
prefix.append(float(prefix[-1] + nums[i]))
mavg = prefix[-1]/k
lbound = -1
for i in range(k,len(nums)):
prefix.append(prefix[-1] + nums[i])
cavg = (prefix[i+1] - prefix[lbound+1])/(i-lbound)
altavg = (prefix[i+1] - prefix[i-k+1])/k
if altavg > cavg:
lbound = i-k
cavg = altavg
mavg = max(mavg, cavg)

return mavg
``````

Please let me know if you see any issues here.

• @awice, @agave, @StefanPochmann do you see any issues here?

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