Maximum Average Subarray I
EasyPrompt
You are given an integer array nums consisting of n elements, and an integer k.
Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.
Example 1:
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.75Example 2:
Input: nums = [5], k = 1
Output: 5.00000
Constraints:
n == nums.length1 <= k <= n <= 105-104 <= nums[i] <= 104
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through every possible contiguous subarray of length k, calculates the sum of each subarray, and finds the maximum sum. The maximum average is then this maximum sum divided by k.
Algorithm
- Initialize a variable
maxSumto a very small number (e.g.,Long.MIN_VALUE). - Iterate with an index
ifrom0ton-k, wherenis the length of the array. This indexiwill be the starting point of our subarray. - For each
i, create an inner loop with indexjfromitoi+k-1to calculate the sum of the current subarray. - Store this sum in a variable
currentSum. - After the inner loop, compare
currentSumwithmaxSumand updatemaxSum = Math.max(maxSum, currentSum). - After the outer loop finishes, return
maxSum / k.
Walkthrough
The simplest way to solve this problem is to consider every possible subarray of length k one by one.
We can use a nested loop structure. The outer loop iterates through all possible starting indices of the subarray, from 0 to n-k.
For each starting index i, the inner loop calculates the sum of the elements from nums[i] to nums[i+k-1].
We maintain a variable, say maxSum, to store the maximum sum found so far. After calculating the sum of a subarray, we compare it with maxSum and update maxSum if the current sum is greater.
After the loops complete, maxSum will hold the maximum sum of any contiguous subarray of length k. The final result is maxSum / k.
public class Solution { public double findMaxAverage(int[] nums, int k) { long maxSum = Long.MIN_VALUE; int n = nums.length; for (int i = 0; i <= n - k; i++) { long currentSum = 0; for (int j = i; j < i + k; j++) { currentSum += nums[j]; } maxSum = Math.max(maxSum, currentSum); } return (double) maxSum / k; }}Complexity
Time
O(n * k). The outer loop runs `n-k+1` times, and for each iteration, the inner loop runs `k` times to calculate the sum. This results in a total of approximately `n * k` operations.
Space
O(1). We only use a few variables to store the sums and loop indices, regardless of the input size.
Trade-offs
Pros
Simple to understand and implement.
Cons
Inefficient for large inputs, likely to result in a 'Time Limit Exceeded' error on competitive programming platforms due to the O(n*k) complexity.
This approach involves pre-computing a cumulative sum array (also known as a prefix sum array). This allows for the calculation of the sum of any contiguous subarray in constant time. We then iterate through all possible subarrays of length k, calculate their sums using the pre-computed array, and find the maximum.
Algorithm
- Create a
prefixSumarray of sizen+1and initialize all its elements to 0. - Iterate through the
numsarray fromi=0ton-1and populate theprefixSumarray:prefixSum[i+1] = prefixSum[i] + nums[i]. - Initialize a variable
maxSumto a very small number. - Iterate from
i=0ton-k. - For each
i, calculate the sum of the subarraynums[i...i+k-1]ascurrentSum = prefixSum[i+k] - prefixSum[i]. - Update
maxSum = Math.max(maxSum, currentSum). - After the loop, return
maxSum / k.
Walkthrough
The core idea is to create an auxiliary array, let's call it prefixSum, where prefixSum[i] stores the sum of all elements from the beginning of the original array up to index i-1.
The prefixSum array can be built in a single pass through the nums array: prefixSum[i] = prefixSum[i-1] + nums[i-1].
Once we have this prefixSum array, the sum of any subarray from index i to j (inclusive) can be found in O(1) time using the formula prefixSum[j+1] - prefixSum[i].
For our problem, we need the sum of subarrays of length k. A subarray starting at i ends at i+k-1. Its sum is prefixSum[i+k] - prefixSum[i].
We can iterate from i = 0 to n-k, calculate the sum for each subarray of length k using the prefix sum array, and keep track of the maximum sum.
The final result is the maximum sum found divided by k.
public class Solution { public double findMaxAverage(int[] nums, int k) { int n = nums.length; long[] prefixSum = new long[n + 1]; for (int i = 0; i < n; i++) { prefixSum[i + 1] = prefixSum[i] + nums[i]; } long maxSum = Long.MIN_VALUE; for (int i = 0; i <= n - k; i++) { long currentSum = prefixSum[i + k] - prefixSum[i]; maxSum = Math.max(maxSum, currentSum); } return (double) maxSum / k; }}Complexity
Time
O(n). It takes O(n) to build the prefix sum array and another O(n) to iterate through the subarrays to find the maximum sum. The total complexity is O(n) + O(n) = O(n).
Space
O(n). We need an additional array of size `n+1` to store the cumulative sums.
Trade-offs
Pros
Efficient O(n) time complexity.
Conceptually separates the sum calculation from the search for the maximum.
Cons
Requires extra space proportional to the input size, which is less space-efficient than the sliding window approach.
A more efficient approach is to use the sliding window technique. Instead of re-calculating the sum of each subarray from scratch, we can calculate the sum of the next subarray in constant time by subtracting the element that leaves the window and adding the element that enters the window.
Algorithm
- Calculate the sum of the first
kelements and store it in a variablewindowSum. - Initialize
maxSumwith the value ofwindowSum. - Iterate from index
kton-1(wherenis the length of the array). - In each iteration
i, updatewindowSumby adding the current elementnums[i]and subtracting the element that just left the window,nums[i-k]. The formula iswindowSum = windowSum + nums[i] - nums[i-k]. - Update
maxSum = Math.max(maxSum, windowSum). - After the loop, return
maxSum / k.
Walkthrough
This method avoids the redundant calculations of the brute-force approach. We start by computing the sum of the first k elements.
We initialize two variables: windowSum for the sum of the current window and maxSum to keep track of the maximum sum found so far. Both are initialized with the sum of the first k elements.
Then, we iterate through the array from the k-th element to the end. In each iteration, we 'slide' the window one step to the right.
This is done by adding the new element nums[i] to windowSum and subtracting the element that is no longer in the window, nums[i-k].
After updating windowSum, we compare it with maxSum and update maxSum if windowSum is larger.
Finally, after iterating through the entire array, we return maxSum / k.
public class Solution { public double findMaxAverage(int[] nums, int k) { long sum = 0; for (int i = 0; i < k; i++) { sum += nums[i]; } long maxSum = sum; for (int i = k; i < nums.length; i++) { sum += nums[i] - nums[i - k]; maxSum = Math.max(maxSum, sum); } return (double) maxSum / k; }}Complexity
Time
O(n). We calculate the sum of the first `k` elements in O(k) time. Then, we iterate through the rest of the array once, which takes O(n-k) time. The total time complexity is O(k + n - k) = O(n).
Space
O(1). We only use a constant amount of extra space for variables like `windowSum` and `maxSum`.
Trade-offs
Pros
Highly efficient with linear time complexity.
Optimal solution for this problem in terms of both time and space.
Cons
Slightly more complex to reason about than the brute-force approach, but it's a standard and important technique.
Solutions
Solution
class Solution {public double findMaxAverage(int[] nums, int k) { int s = 0; for (int i = 0; i < k; ++i) { s += nums[i]; } int ans = s; for (int i = k; i < nums.length; ++i) { s += (nums[i] - nums[i - k]); ans = Math.max(ans, s); } return ans * 1.0 / k; }}class Solution {public: double findMaxAverage(vector<int> &nums, int k) { int s = accumulate(nums.begin(), nums.begin() + k, 0); int ans = s; for (int i = k; i < nums.size(); ++i) { s += nums[i] - nums[i - k]; ans = max(ans, s); } return static_cast<double>(ans) / k; }};class Solution: def findMaxAverage(self, nums: List[int], k: int) -> float: s = sum(nums[: k]) ans = s for i in range(k, len(nums)): s += nums[i] - nums[i - k] ans = max(ans, s) return ans / kVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.