Max Average Subarray — Problem Statement & Solution Guide
Problem Description
Given an array of integers nums and an integer k, determine the maximum average value among all contiguous subarrays of length k. Return the floor of this maximum average multiplied by 100000. The input consists of the array nums and the integer k. The output is a single integer representing the truncated scaled maximum average.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Max Average Subarray"
WHY DOES IT MATTER?
Sliding window is essential for problems involving contiguous subarrays with a fixed or bounded size because it allows linear-time solutions by reusing previous computations. It reduces redundant work and is a go-to pattern in coding interviews for its simplicity and efficiency.
OPTIMIZATION CHALLENGE
The key insight is that the sum of the next window can be derived from the current window by subtracting the element that exits and adding the new element that enters, eliminating the need for a nested loop. This reduces time from O(nk) to O(n) and space from O(n) to O(1).
REAL-WORLD CONNECTION
Think of a streaming sensor that reports temperature every minute. To compute the average temperature over the last 10 minutes at any point, you keep a rolling sum of the last 10 readings and update it as new data arrives—exactly the sliding window technique.
When explaining the solution, emphasize the invariant: the window sum always equals the sum of the last k elements. Highlight that the maximum average corresponds to the maximum window sum, which can be tracked in a single pass.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The Max Average Subarray problem is a classic example of the sliding window paradigm. By maintaining a running sum of the current window of size k, we can compute the average of each subarray in constant time, updating the sum as we slide the window one element at a time. This approach eliminates the need to recompute sums from scratch for each subarray, which would otherwise require O(nk) time and become infeasible for large arrays.
A naive solution would iterate over every possible starting index, sum k elements for each subarray, and track the maximum average. This results in O(nk) time complexity and O(1) space, but the nested loop makes it too slow when n is large (e.g., 10^5 or more). The sliding window technique reduces the time complexity to O(n) by reusing the previous sum and only adding the new element while subtracting the element that leaves the window.
The optimal algorithm also handles the scaling requirement—returning the floor of the maximum average multiplied by 100000—by computing the maximum sum of any k-length subarray and then performing integer division by k, followed by multiplication by 100000. This avoids floating-point inaccuracies and ensures the result is an integer as specified.
Interview Questions on This Problem
Q1How would you modify the algorithm if the subarray length k were not fixed but instead you needed the maximum average over any subarray of length at least k?
You would use a two-pointer or expanding window approach, maintaining a running sum and length while expanding the window until the average starts decreasing. Alternatively, you could precompute prefix sums and use a binary search over possible average values, checking feasibility with a transformed array. This transforms the problem into a decision problem solvable in O(n log V) time, where V is the range of possible averages.
Q2A candidate suggests using a priority queue to keep track of the k largest elements seen so far. Why is this approach incorrect for this problem?
The maximum average subarray depends on the sum of consecutive elements, not on the k largest elements globally. A priority queue would ignore the contiguity constraint and could produce a subarray that is not contiguous, leading to an incorrect answer.
Q3During an interview, a candidate proposes using a prefix sum array and then iterating over all pairs of indices to compute averages. What is the time complexity of this approach and why is it suboptimal?
The approach would have O(n^2) time complexity because for each start index you would compute the sum for all possible end indices. This is far slower than the O(n) sliding window method and would time out on large inputs.
Examples
Input
[1,12,-5,-6,50,3],4
Output
1275000
Explanation: Compute sums of all windows of length 4: [1+12-5-6=2], [12-5-6+50=51], [-5-6+50+3=42]. The maximum sum is 51, giving an average of 51/4=12.75. Multiply by 100000 to get 1275000 and truncate to the integer 1275000.
Input
[-1,-2,-3,-4],2
Output
-150000
Explanation: Window sums: [-1-2=-3], [-2-3=-5], [-3-4=-7]. The maximum sum is -3, average -1.5. Multiply by 100000 to get -150000 and truncate to -150000.
Input
[5,5,5,5,5],3
Output
500000
Explanation: All windows of length 3 sum to 15, average 5. Multiply by 100000 gives 500000.
Input
[10,-10,20,-20,30,-30],2
Output
300000
Explanation: Window sums: [10-10=0], [-10+20=10], [20-20=0], [-20+30=10], [30-30=0]. The maximum sum is 10, average 5. Multiply by 100000 gives 500000. However, the window [20,-20] yields 0, so the maximum average is 5. The correct output is 500000.
Constraints
- 1 <= nums.length <= 100000
- 1 <= k <= nums.length
- -1000000000 <= nums[i] <= 1000000000
Optimal Approach & Strategy
Maintain a running sum of the current k-length window, update it by subtracting the element leaving and adding the new one, track the maximum sum, then compute the scaled floor average. This runs in O(n) time and O(1) space.
Brute Force Approach
Compute the sum of every subarray of length k by nested loops, track the maximum sum, then divide by k and scale. This takes O(nk) time and O(1) space.
Verified Code Solutions
const nums = [1,12,-5,-6,50,3];
const k = 4;
let sum = 0, maxSum = -Infinity;
for(let i=0;i<k;i++) sum += nums[i];
maxSum = sum;
for(let i=k;i<nums.length;i++){
sum += nums[i] - nums[i-k];
if(sum > maxSum) maxSum = sum;
}
const avg = maxSum / k;
const result = Math.floor(avg * 100000);
console.log(result);#include <bits/stdc++.h>
using namespace std;
int main(){
vector<int> nums = {1,12,-5,-6,50,3};
int k = 4;
long long sum = 0, maxSum = LLONG_MIN;
for(int i=0;i<k;i++) sum += nums[i];
maxSum = sum;
for(int i=k;i<nums.size();i++){
sum += nums[i] - nums[i-k];
if(sum > maxSum) maxSum = sum;
}
double avg = (double)maxSum / k;
long long result = (long long)floor(avg * 100000.0 + 1e-9);
cout << result << endl;
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
int[] nums = {1,12,-5,-6,50,3};
int k = 4;
long sum = 0, maxSum = Long.MIN_VALUE;
for(int i=0;i<k;i++) sum += nums[i];
maxSum = sum;
for(int i=k;i<nums.length;i++){
sum += nums[i] - nums[i-k];
if(sum > maxSum) maxSum = sum;
}
double avg = (double)maxSum / k;
long result = (long)Math.floor(avg * 100000.0 + 1e-9);
System.out.println(result);
}
}nums = [1,12,-5,-6,50,3]
k = 4
sum_ = sum(nums[:k])
max_sum = sum_
for i in range(k, len(nums)):
sum_ += nums[i] - nums[i-k]
if sum_ > max_sum:
max_sum = sum_
avg = max_sum / k
result = int(avg * 100000)
print(result)const nums = [1,12,-5,-6,50,3];
const k = 4;
let sum = 0, maxSum = -Infinity;
for(let i=0;i<k;i++) sum += nums[i];
maxSum = sum;
for(let i=k;i<nums.length;i++){
sum += nums[i] - nums[i-k];
if(sum > maxSum) maxSum = sum;
}
const avg = maxSum / k;
const result = Math.floor(avg * 100000);
console.log(result);Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.