Maximum Average Subarray I
Asked at Amazon
Problem
Given an integer array nums and an integer k, find a contiguous subarray of length k that has the maximum average value. Return the maximum average value. This is a straightforward application of the fixed-size sliding window pattern.
Asked At
| Company | Difficulty | |
|---|---|---|
| Amazon | EASY | View all Amazon questions → |
How to Think About It
Brute force: compute the sum of every subarray of length k and track the maximum.
Optimize by sliding the window: subtract the element leaving and add the element entering.
Precompute the prefix sum of the first k elements as the initial window sum.
Slide the window one position at a time updating the sum in O(1).
Return the maximum sum divided by k. Time O(n), space O(1).
Optimal Approach
Compute the sum of the first k elements. Then slide the window one element at a time: add the new element on the right and subtract the element that falls off on the left. Track the maximum sum seen. The answer is the maximum sum divided by k. This runs in O(n) time with O(1) space. The fixed window makes this simpler than variable-size sliding window problems.
What Trips People Up in Real Interviews
Confirm that k is guaranteed to be less than or equal to nums.length.
Ask whether floating point precision matters for the average.
Mention that this is a fixed-size sliding window (unlike variable-size variants).
Edge cases: k equals 1 (return max element), k equals n (return total average).
Code the sum update pattern: sum += nums[i] - nums[i - k] to avoid recomputation.
Solution Code
def findMaxAverage(nums, k):
window_sum = sum(nums[:k])
max_sum = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k]
max_sum = max(max_sum, window_sum)
return max_sum / kFrequently Asked Questions
What is the Maximum Average Subarray I problem?
Given an integer array nums and an integer k, find a contiguous subarray of length k that has the maximum average value. Return the maximum average value. This is a straightforward application of the fixed-size sliding window pattern.
How do you solve Maximum Average Subarray I?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Maximum Average Subarray I?
Maximum Average Subarray I is asked at Amazon. It is a easy difficulty problem.
What are common mistakes on Maximum Average Subarray I?
- Confirm that k is guaranteed to be less than or equal to nums.length.
- Ask whether floating point precision matters for the average.
- Mention that this is a fixed-size sliding window (unlike variable-size variants).
- Edge cases: k equals 1 (return max element), k equals n (return total average).
- Code the sum update pattern: sum += nums[i] - nums[i - k] to avoid recomputation.