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

Related Posts

• Leetcode 424 - Longest Repeating Character Replacement
• I’ve never done a leetcode problem before in my life, but I program every single day. I was recommended this sub, and I have a question after seeing the seriousness of leetcoders.
• Two Sum and Its Variants
• Leetcode 1004 - Max Consecutive Ones III
• Leetcode 222 - Count Complete Tree Nodes
• Leetcode 1027 - Longest Arithmetic Subsequence
• Question 1299 on leetcode
• Leetcode 240 - Search a 2D Matrix II
• Leetcode 1351 - Count Negative Numbers in a Sorted Matrix
• Leetcode 239 - Sliding Window Maximum
• Leetcode 209 - Minimum Size Subarray Sum
• LeetCode 230 - Kth Smallest Element in a BST with Code
• advanced-applications-of-binary-search
• Leetcode 96 - Unique Binary Search Trees
• Leetcode 540 - Single Element in a Sorted Array
• Leetcode 1283 - Find the Smallest Divisor Given a Threshold
• Leetcode 74 - Search a 2D Matrix
• Leetcode 300 - Longest Increasing Subsequence
• Leetcode 930 - Binary Subarrays With Sum
• Blazingly fast solution to LeetCode #1342 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (Cross-post from r/SoftwareEngineering)
• Leetcode 704 - Binary Search
• LeetCode - Two Sum Solution with Code
• a-binary-search-template
• Leetcode 1358 - Number of Substrings Containing All Three Characters
• Leetcode 33 - Search in Rotated Sorted Array
• Leetcode 1151 - Minimum Swaps to Group All 1’s Together