Maximum Average Subarray I

Given an integer array nums and an integer k, find the maximum average value of any continuous subarray of size k.

A subarray is a contiguous part of the array.

Return the maximum average value among all subarrays of size k.

If no subarray of size k exists, return 0.0.

Brute Force Approach

Every valid starting index defines one contiguous subarray of size k. Calculating the sum of k consecutive elements from every starting index guarantees examination of all valid subarrays.

Dividing each sum by k produces the corresponding average. Overlapping subarrays contain common elements, so repeated calculation performs many unnecessary additions.

Algorithm

• Store the array size in n and return 0.0 when k <= 0 or n < k.

• Initialize maxAverage with the smallest possible value to support arrays containing only negative numbers.

• Traverse every valid starting index i from 0 to n - k.

• Initialize currentSum with 0 and add elements from index i through i + k - 1.

• Calculate currentAverage as currentSum / k and update maxAverage when currentAverage is larger.

• Return maxAverage after processing every subarray of size k.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N × K), where N represents the array size. Every valid starting index may require addition of K elements.

Space Complexity: O(1), because only loop indices, currentSum, currentAverage, and maxAverage require auxiliary storage.

Better Approach

A prefix sum array stores cumulative sums from the beginning of nums. The value at prefixSum[i] represents the sum of the first i elements.

For a subarray starting at index i and ending at index i + k - 1, subtracting prefixSum[i] from prefixSum[i + k] removes every element before index i. Each fixed-size subarray sum can therefore be calculated in constant time.

Algorithm

• Store the array size in n and return 0.0 when k <= 0 or n < k.

• Create prefixSum with size n + 1 and initialize prefixSum[0] with 0.

• Traverse nums and calculate prefixSum[i + 1] = prefixSum[i] + nums[i].

• Initialize maxAverage with the smallest possible value.

• Traverse every starting index i from 0 to n - k, calculate currentSum = prefixSum[i + k] - prefixSum[i], and calculate currentAverage = currentSum / k.

• Update maxAverage for every valid subarray and return maxAverage after complete traversal.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N), where N is the size of the array. The prefix sum array is built once, and every subarray sum of size k is calculated in constant time.

Space Complexity: O(N), because an extra prefix sum array of size n + 1 is used.

Optimal Approach

A fixed-size sliding window begins with the first k elements. Moving the window one position forward removes the leftmost element and adds one new element from the right.

Every window contains the same number of elements. Therefore, the window with the maximum sum also has the maximum average. Tracking sums avoids repeated division during traversal, and one final division produces the required result.

Algorithm

• Store the array size in n and return 0.0 when k <= 0 or n < k.

• Initialize windowSum with 0 and add the first k elements to form the first valid window.

• Initialize maxSum with windowSum because the first window provides the first valid candidate.

• Traverse i from k to n - 1, where nums[i] is the new element entering the window and nums[i - k] is the leftmost element leaving the previous window.

• Update windowSum by adding nums[i] and subtracting nums[i - k], then update maxSum whenever the new window produces a larger sum.

• Return maxSum / k using floating-point division after processing every window.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N), where N represents the array size. Initial window construction processes K elements, while the remaining traversal processes every later element once.

Space Complexity: O(1), because only windowSum, maxSum, and loop variables require auxiliary storage.

FAQS

Q1. Why does invalid k return 0.0?

A non-positive k cannot represent a valid subarray length, while k > N cannot fit inside the array. The supplied problem contract uses 0.0 for both cases.

Q2. Why does the prefix sum array contain N + 1 positions?

The leading zero allows subarrays starting at index 0 to use the same subtraction formula as every other subarray.

Q3. Why does the Optimal Approach track maximum sum instead of maximum average?

Every candidate contains exactly K elements. Division by the same positive value preserves the ordering of all window sums.

Q4. Why is nums[i - k] subtracted during window movement?

Index i - k identifies the outgoing leftmost element from the previous window. Subtracting it keeps exactly K elements in the current window.

Q5. Does the solution support negative numbers?

Yes. Initializing the maximum from the first valid window prevents an incorrect default answer of 0 when every valid average is negative.

Q6. What happens if we calculate the average for every window instead of tracking its sum?

The result remains correct because every window contains exactly K elements. However, calculating the average repeatedly performs unnecessary floating-point division. Tracking sums and dividing only once at the end gives the same answer more simply.