Log inSign up
easyLeetCodeNot Started

Maximum Average Subarray I

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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 · Standard Array with Mixed Values:

Input: nums = [1, 12, -5, -6, 50, 3], k = 4
Output: 12.75000
Explanation: Subarrays of length 4 and their sums: - [1, 12, -5, -6] -> sum = 2, avg = 0.5 - [12, -5, -6, 50] -> sum = 51, avg = 12.75 - [-5, -6, 50, 3] -> sum = 42, avg = 10.5 The maximum average is 12.75.

Example 2 · Single Element Array:

Input: nums = [5], k = 1
Output: 5.00000
Explanation: The only subarray of length 1 is [5]. Maximum average is 5 / 1 = 5.0.

Example 3 · All Negative Numbers:

Input: nums = [-1, -12, -5, -6], k = 2
Output: -5.50000
Explanation: Subarrays of length 2: - [-1, -12] -> sum = -13, avg = -6.5 - [-12, -5] -> sum = -17, avg = -8.5 - [-5, -6] -> sum = -11, avg = -5.5 Maximum average is -5.5.

Constraints:

  • n == nums.length
  • 1 <= k <= n <= 105
  • -104 <= nums[i] <= 104

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Array indexing and contiguous subarray concepts
  • Understanding the Sliding Window pattern
  • Floating-point division and integer overflow awareness

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the Fixed-Size Sliding Window pattern: add incoming, remove outgoing.
  • Avoid recomputing window sums from scratch, reducing time from O(N * k) to O(N).
  • Avoid precision and overflow bugs by tracking the maximum sum as an integer and dividing by k once at the end.
  • Implement clean solutions across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Problem requires finding a contiguous subarray of FIXED length k.
  • Asked to maximize or minimize a property (sum, average) over every window of size k.
  • Adjacent windows share k - 1 overlapping elements.

Algorithmic Decision Tree:

  • Whenever a problem asks for an aggregate (sum/max/min) over contiguous subarrays of fixed length k: Use Fixed-Size Sliding Window.
  • Maintain a running sum: windowSum += nums[i] - nums[i - k].

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Brute Force — Recomputing Each Window

Intuition

Iterate over every possible starting index i and calculate the sum of the k elements starting at i using an inner loop.

Algorithm

  1. Initialize maxSum = -infinity.
  2. Loop i from 0 to nums.length - k:
  3. currentSum = 0.
  4. Loop j from i to i + k - 1:
  5. currentSum += nums[j].
  6. maxSum = max(maxSum, currentSum).
  7. Return maxSum / k as a double.

Recompute Each Window Sum (O(N*K) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Compute the sum of elements from index 0 to 3 manually
Visual state
Values and pointers at this exact step
pointers
S
1
12
-5
-6
50
3
0
↑ start
1
2
3
↑ end
4
5
Variables at this step
start
0
end
3
currentSum
2
currentAvg
0.5
maxSum
2
maxAvg
0.5
Check / comparison
Sum window [0..3]: 1 + 12 + (-5) + (-6) = 2
Decision / next transition
Average = 2 / 4 = 0.5. Initialize maxAvg = 0.5, maxSum = 2.
Why this step matters

Compute the sum of elements from index 0 to 3 manually.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <algorithm>
2#include <climits>
3#include <iomanip>
4#include <iostream>
5#include <vector>
6using namespace std;
7
8// Brute Force: Recompute sum for every window of size k
9double findMaxAverage(vector<int>& nums, int k) {
10 int n = nums.size();
11 long long maxSum = LLONG_MIN;
12
13 for (int i = 0; i <= n - k; i++) {
14 long long currentSum = 0;
15 for (int j = i; j < i + k; j++) {
16 currentSum += nums[j];
17 }
18 maxSum = max(maxSum, currentSum);
19 }
20
21 return (double)maxSum / k;
22}
23
24int main() {
25 vector<int> nums = {1, 12, -5, -6, 50, 3};
26 int k = 4;
27 cout << fixed << setprecision(5);
28 cout << "Output: " << findMaxAverage(nums, k) << endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Approach 1: Brute Force — Recomputing Each Window.
  • Space complexity: O(1) — Space complexity for Approach 1: Brute Force — Recomputing Each Window.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Better — Prefix Sum Array

Intuition

Precompute a prefix sum array in O(N). Then evaluate the sum of every length-k subarray in O(1) time using range queries.

Algorithm

  1. Create a prefix array prefix of size n + 1 with prefix[0] = 0.
  2. Fill prefix[i] = prefix[i - 1] + nums[i - 1] for i = 1 to n.
  3. Initialize maxSum = prefix[k] - prefix[0].
  4. For i = 1 to n - k:
  5. windowSum = prefix[i + k] - prefix[i].
  6. maxSum = max(maxSum, windowSum).
  7. Return maxSum / k.

Prefix Sum Array (O(N) Time, O(N) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Prefix array construction takes O(N) time and allows constant time window sum queries
Visual state
Values and pointers at this exact step
pointers
S
0
1
13
8
2
52
55
0
↑ P
1
2
3
4
5
6
Variables at this step
prefixBuilt
true
k
4
maxSum
null
Check / comparison
Build 1-based prefix sum array: P = [0, 1, 13, 8, 2, 52, 55]
Decision / next transition
Any window [i..i+k-1] sum is calculated as P[i+k] - P[i].
Why this step matters

Prefix array construction takes O(N) time and allows constant time window sum queries.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <algorithm>
2#include <iomanip>
3#include <iostream>
4#include <vector>
5using namespace std;
6
7// Better: Prefix Sum Array in O(N) time and O(N) space
8double findMaxAverage(vector<int>& nums, int k) {
9 int n = nums.size();
10 vector<long long> prefix(n + 1, 0);
11
12 for (int i = 0; i < n; i++) {
13 prefix[i + 1] = prefix[i] + nums[i];
14 }
15
16 long long maxSum = prefix[k] - prefix[0];
17 for (int i = 1; i <= n - k; i++) {
18 long long currentSum = prefix[i + k] - prefix[i];
19 maxSum = max(maxSum, currentSum);
20 }
21
22 return (double)maxSum / k;
23}
24
25int main() {
26 vector<int> nums = {1, 12, -5, -6, 50, 3};
27 int k = 4;
28 cout << fixed << setprecision(5);
29 cout << "Output: " << findMaxAverage(nums, k) << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Approach 2: Better — Prefix Sum Array.
  • Space complexity: O(N) — Space complexity for Approach 2: Better — Prefix Sum Array.

3. Optimal — Fixed-Size Sliding Window (O(1) Space)

Intuition

Compute the sum of the first k elements, then slide the window across the array by adding nums[i] and subtracting nums[i - k] in O(1) space.

Algorithm

  1. Calculate the sum of the first k elements and store in windowSum.
  2. Set maxSum = windowSum.
  3. Loop i from k to nums.length - 1:
  4. windowSum += nums[i] - nums[i - k].
  5. maxSum = max(maxSum, windowSum).
  6. Return maxSum / k.

Sliding Window in O(1) Space (O(N) Time, O(1) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Only sum the initial k elements once
Visual state
Values and pointers at this exact step
pointers
S
1
12
-5
-6
50
3
0
↑ L
1
2
3
↑ R
4
5
Variables at this step
L
0
R
3
windowSum
2
maxSum
2
Check / comparison
Initialize first window [0..3]: sum = 1 + 12 + (-5) + (-6) = 2
Decision / next transition
windowSum = 2, maxSum = 2.
Why this step matters

Only sum the initial k elements once. All subsequent transitions cost O(1).

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <algorithm>
2#include <iomanip>
3#include <iostream>
4#include <vector>
5using namespace std;
6
7// Optimal: Fixed-Size Sliding Window in O(N) time and O(1) space
8double findMaxAverage(vector<int>& nums, int k) {
9 long long windowSum = 0;
10
11 // Compute sum of first k elements
12 for (int i = 0; i < k; i++) {
13 windowSum += nums[i];
14 }
15
16 long long maxSum = windowSum;
17
18 // Slide window across array
19 for (size_t i = k; i < nums.size(); i++) {
20 windowSum += nums[i] - nums[i - k];
21 maxSum = max(maxSum, windowSum);
22 }
23
24 return (double)maxSum / k;
25}
26
27int main() {
28 vector<int> nums = {1, 12, -5, -6, 50, 3};
29 int k = 4;
30 cout << fixed << setprecision(5);
31 cout << "Output: " << findMaxAverage(nums, k) << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Approach 3: Optimal — Fixed-Size Sliding Window (O(1) Space).
  • Space complexity: O(1) — Space complexity for Approach 3: Optimal — Fixed-Size Sliding Window (O(1) Space).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force (Nested Sum)O(N * k)O(1)Straightforward to write.Baseline only.
2.Prefix Sum ArrayO(N)O(N)O(1) range sum queries, standard pattern for multiple queries.Good alternative; interviewer will ask to optimize memory to O(1).
3.Fixed-Size Sliding WindowOptimalO(N)O(1)Optimal linear time, strictly O(1) memory, clean implementation.Optimal gold standard.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • k Equals Array Length (k == n) — Input: nums = [1, 2, 3, 4], k = 4, Expected: 2.50000 — When k == n, the loop sliding the window doesn't execute; ensure the initial sum is returned divided by k.
  • All Negative Numbers — Input: nums = [-5, -10, -15], k = 2, Expected: -7.50000 — Initializing maxSum to 0 will fail for all-negative inputs. Initialize maxSum to the sum of the first window.
  • Single Element Array (k == 1) — Input: nums = [7], k = 1, Expected: 7.00000 — Returns the single element as a double immediately.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Pattern Identification — State immediately: 'This is a textbook Fixed-Size Sliding Window problem because the subarray size k is constant.'
  2. Edge Cases to Mention — Mention negative numbers and integer overflow: 'I will initialize maxSum with the first window's sum rather than 0 to handle negative inputs, and use 64-bit integers to prevent overflow.'
  3. Follow-up — Be prepared for dynamic sliding window follow-ups like 'Minimum Size Subarray Sum' where window size varies.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Maximum Average Subarray I?

2.Why is the brute force approach suboptimal for large inputs in Maximum Average Subarray I?

3.Which data structure or technique enables the optimal solution for Maximum Average Subarray I?

Back to DSA Sheet