Maximum Average Subarray I

The Sliding Window Pattern: A Fixed-Size Approach

The sliding window pattern is an incredibly useful algorithmic technique, particularly for problems involving arrays or lists where you need to perform an operation on a contiguous subarray (or substring) of a specific size. Imagine you have a window of a fixed width, and you “slide” this window across your data structure, one element at a time. Instead of recalculating the entire sum or property of the window at each step, you efficiently update it by removing the element that leaves the window and adding the new element that enters. This approach significantly reduces redundant calculations and optimizes the solution’s performance.

When we talk about a fixed-size sliding window, it means the k (the size of the window) remains constant throughout the algorithm’s execution. This is a common scenario in problems where you’re looking for things like maximum/minimum sum subarrays of a certain length, averages, or specific counts within a defined range.

---

Problem: Maximum Average Subarray I

Given an array of integers nums and an integer k, find a contiguous subarray whose length is equal to k that has the maximum average value. You need to return this maximum average 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

---

Solution

from typing import List
 
class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        start = 0
        current_sum = 0
        maxAvg = float('-inf')
        for end in range(len(nums)):
            current_sum += nums[end]
            if(end-start+1 == k):
                maxAvg = max(maxAvg, current_sum / k)
                current_sum -= nums[start]
                start += 1
        return maxAvg

---

Explanation of the Algorithm

The provided solution effectively uses the fixed-size sliding window pattern to solve the “Maximum Average Subarray I” problem. Let’s break down the algorithm step-by-step to understand its logic and efficiency.

1. Initialization:

   • start: This pointer marks the beginning of our current sliding window. It starts at the first element of the array.
   • current_sum: This variable will keep track of the sum of all elements within the current window.
   • maxAvg: We initialize maxAvg to negative infinity. This is a common practice to ensure that the very first average we calculate (which will be a valid number) will always be greater than maxAvg and thus correctly set as the initial maximum.

2. Window Expansion and Calculation (The for loop):

   • The for end in range(len(nums)): loop iterates through the entire nums array using the end pointer. This end pointer effectively expands our window to the right.
   • current_sum += nums[end]: In each iteration, the element at the end index is added to current_sum. This continuously updates the sum to include the newest element entering the window.

3. Window Size Check (if (end - start + 1 == k)):

   • This is the crucial step where we check if our window has reached the desired fixed size k.
   • end - start + 1 calculates the current length of the window (number of elements from start to end, inclusive).
   • Once this length equals k, it means we have a complete window of the specified size.

4. Process and Slide:

   • Calculate Average: maxAvg = max(maxAvg, current_sum / k): If the window is of size k, we calculate its average (current_sum / k) and compare it with the maxAvg found so far. We update maxAvg to store the larger of the two.
   • Remove Oldest Element: current_sum -= nums[start]: To “slide” the window to the right, we must remove the element that is now leaving the window from the current_sum. The element at the start index is the one exiting the window as we move forward.
   • Advance Window Start: start += 1: Finally, we increment the start pointer. This officially moves the window one position to the right, preparing it for the next iteration where a new element will be added at the end and the window will once again be of size k.

5. Return Result:

   • After the for loop completes, maxAvg will hold the maximum average found among all contiguous subarrays of length k. The function then returns this value.

Efficiency:

• Time Complexity: O(n) The algorithm iterates through the nums array only once with the end pointer. The operations inside the loop (addition, subtraction, comparison, division) are all constant time operations. Therefore, the time complexity is linear with respect to the number of elements in the array, making it very efficient for large inputs.
• Space Complexity: O(1) The algorithm uses a few constant extra variables (start, current_sum, maxAvg). The amount of extra space required does not grow with the size of the input array, hence the space complexity is constant.

This fixed-size sliding window approach is a powerful and elegant way to solve many array-based problems by avoiding redundant calculations and achieving optimal performance.