Introduction

The Maximum Average Subarray I problem asks us to find the contiguous subarray of exactly k elements that has the highest average.

Since every possible subarray has the same length k, we can efficiently solve the problem using the Sliding Window technique.

Problem Statement

Given an integer array nums and an integer k, find a contiguous subarray of length k that has the maximum average.

Return the maximum average.

Example

Input:nums = [1, 12, -5, -6, 50, 3]
k = 4

Output:
12.75

Explanation:
The subarray [12, -5, -6, 50] has:
Sum = 12 + (-5) + (-6) + 50 = 51
Average = 51 / 4 = 12.75
Therefore, the maximum average is 12.75.

Constraints

  • 1 ≤ k ≤ n
  • n = nums.length
  • 1 ≤ n ≤ 10⁵
  • -10⁴ ≤ nums[i] ≤ 10⁴
  • The answer should be accurate within 10⁻⁵.

Premium Video

This video is available to Premium members or users who have purchased the course.

Sign in to Unlock

Approach 1: Brute Force

Explanation

We can check every possible subarray of length k.

For each starting position:

  1. Calculate the sum of the next k elements.
  2. Calculate their average.
  3. Compare it with the current maximum average.
  4. Continue until all possible subarrays are checked.

Since we calculate the sum of k elements for every window, this approach takes O(n × k) time.

Steps

  1. Start from the first possible index.
  2. Calculate the sum of k consecutive elements.
  3. Calculate the average.
  4. Update the maximum average.
  5. Move to the next starting position.
  6. Repeat until all windows are processed.

Dry Run

nums = [1, 12, -5, -6, 50, 3]k = 4

Window 1:
[1, 12, -5, -6]
Sum = 2
Average = 0.5

Window 2:
[12, -5, -6, 50]
Sum = 51
Average = 12.75

Window 3:
[-5, -6, 50, 3]
Sum = 42
Average = 10.5

Maximum Average = 12.75

Brute Force Code


Complexity Analysis

Time Complexity: O(n × k)

Space Complexity: O(1)

Approach 2: Optimized Solution Using Sliding Window

Explanation

The brute-force approach calculates the complete sum for every window.

Instead, we can reuse the previous window's sum.

When the window moves one position:

  • Add the new element entering the window.
  • Remove the element leaving the window.

This updates the sum in O(1) time.

Steps

  1. Calculate the sum of the first k elements.
  2. Store it as the maximum sum.
  3. Move the window one position at a time.
  4. Add the new element.
  5. Remove the outgoing element.
  6. Update the maximum sum.
  7. Divide the maximum sum by k.

Dry Run

nums = [1, 12, -5, -6, 50, 3]k = 4

Initial Window:
[1, 12, -5, -6]
Sum = 2
Maximum Sum = 2

Slide Window:
Add 50
Remove 1

New Window:
[12, -5, -6, 50]
Sum = 2 + 50 - 1 = 51
Maximum Sum = 51

Slide Window:
Add 3
Remove 12

New Window:
[-5, -6, 50, 3]
Sum = 51 + 3 - 12 = 42
Maximum Sum = 51

Maximum Average:
51 / 4 = 12.75

Optimized Code

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Edge Cases

  • k = 1: The maximum average is the maximum element.
  • k = n: The entire array is the only possible window.
  • All elements can be negative.
  • All elements can be positive.
  • The maximum average window can occur anywhere in the array.

Why This Problem is Important

This problem demonstrates how a fixed-size sliding window avoids repeated calculations.

Instead of recalculating the sum of every window, we simply add one element and remove one element.

Real-World Applications

The same technique can be used for:

  • Calculating moving averages.
  • Analyzing rolling performance.
  • Processing fixed-size batches.
  • Monitoring measurements over fixed time periods.
  • Analyzing continuous data streams.

Common Mistakes

  • Recalculating the complete sum for every window.
  • Initializing the maximum sum to 0 when the array can contain negative values.
  • Forgetting to divide the maximum sum by k.
  • Using an incorrect window size.
  • Returning an integer instead of a floating-point result.

Interview Tips

  • Recognize that every candidate subarray has exactly k elements.
  • Think of the problem as finding the maximum sum of a fixed-size window.
  • Initialize the first window separately.
  • When sliding, add the incoming element and remove the outgoing element.
  • Remember that negative values are possible.

Related Questions

  • Maximum Consecutive Ones
  • Maximum Consecutive Ones III
  • Minimum Size Subarray Sum
  • Number of Sub-arrays of Size K and Average ≥ Threshold
  • Subarray Sum Equals K

Final Takeaway

The Brute Force approach checks every k-sized subarray and takes O(n × k) time.

The Sliding Window approach reuses the previous window's sum and reduces the complexity to O(n) time with O(1) extra space.

Key Idea: For a fixed-size window, add the incoming element and remove the outgoing element instead of recalculating the entire sum.