Leetcode 643 - Maximum Average Subarray I

Understanding the problem

The problem statement on LeetCode reads as follows:

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Example 1:

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

Output: 12.75

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

Note:

1 <= k <= n <= 30,000. Elements of the given array will be in the range [-10,000, 10,000].

Plan your solution

One way to solve this problem is to use a sliding window approach. We can iterate through the array, keeping track of the sum of the elements in the current window. At each iteration, we can update the maximum average value if the current window has a greater average than the previous maximum.

Implement your solution

Now that we have a plan, let’s implement it in Python.

def findMaxAverage(nums, k):
    # Edge case: if the array is empty, return 0
    if not nums:
        return 0

    # Initialize the maximum average and the current sum
    max_avg = float('-inf')
    curr_sum = sum(nums[:k])

    # Iterate through the array, updating the maximum average and the current sum
    for i in range(k, len(nums)):
        curr_sum += nums[i] - nums[i-k]
        max_avg = max(max_avg, curr_sum / k)

    return max_avg

Test your solution

Testing is an important step in the software development process as it helps ensure that your code is correct and works as intended. In the case of the “Maximum Average Subarray I” problem, we can test our solution by running a series of test cases that cover different scenarios and edge cases.

For example, we can test our solution with an empty array, an array with one element, an array with multiple elements but no valid subarrays, and an array with multiple elements and one or more valid subarrays. We can also test our solution with arrays of different sizes and with different types of elements (e.g. integers, floats, etc.). By running a variety of test cases, we can gain confidence that our solution is correct and will work for all inputs.

Related:

• single element in a sorted array
• count negative numbers in a sorted matrix
• search in rotated sorted array
• binary search