Python Solution with Detailed Explanation


  • 0
    G

    Maximum Average Subarray I https://leetcode.com/problems/maximum-average-subarray-i/#/description

    Sliding Window Algorithm

    • Initialize sum_so_far as sum of first k elements.
    • Initialize max_so_far to sum_so_far.
    • Now slide to the next window by including next element (say index j) and removing the first of the older window i.e. element at index j-k.
    • Time Complexity is O(N) and Space Complexity is O(1).
    class Solution:
        def findMaxAverage(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: float
            """
            if len(nums) < k:
                return 0.0
            max_so_far = sum_so_far = sum(nums[:k])
            for i in range(k, len(nums)):
                sum_so_far = sum_so_far + nums[i] - nums[i-k]
                max_so_far = max(max_so_far, sum_so_far)
            return float(max_so_far)/k
    

Log in to reply
 

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