643. Maximum Average Subarray I
Asked at Amazon
Difficulty
Easy
Time
O(n)
Space
O(1)
Pattern
Array
Companies
1
Problem
You get an integer array nums and an integer k. Your job is to find a contiguous block of exactly k elements (they must sit next to each other) whose average is as large as possible, and return that maximum average.
Because every block has the same length k, comparing averages is the same as comparing sums. So you can look for the block with the largest sum, then divide that sum by k at the end.
Return the answer as a decimal number. A small rounding error is fine — any answer within 10^-5 of the true value is accepted.
Pick the best block of length k
Constraints
- ●
n == nums.length - ●
1 <= k <= n <= 10^5 - ●
-10^4 <= nums[i] <= 10^4
Examples
nums = [1,12,-5,-6,50,3], k = 412.75000nums = [5], k = 15.00000Asked At
1 companies| 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.
Slide the window one step at a time
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
O(n) timedef 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 runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.