Maximum Average Subarray I — LeetCode 643 Python Solution

The problem

You are given an integer array nums consisting of n elements, and an integer k. Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value.

Example

Input

nums = [1,12,-5,-6,50,3], k = 4

Output

12.75000

Explanation

Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Python solution

from typing import List

def findMaxAverage(nums: List[int], k: int) -> float:
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        if window > best:
            best = window
    return best / k

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 643. Maximum Average Subarray I is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Sliding Window.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems