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


  • 0
    A

    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.


  • 0
    A

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


Log in to reply
 

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