easy Maximum Average Subarray I

Problem Statement

Given an array of integers and an integer k, find a contiguous subarray of length k that has the highest average value, and return this maximum average value.

Examples

Example 1

Input: nums = [1, 2, 3, 4, 5, 6], k = 2
Expected Output: 5.5
Justification: The subarray [5, 6] has the highest average (5 + 6) / 2 = 5.5.

Example 2

Input: nums = [0, 1, 1, 3, -1, 10, -2], k = 3
Expected Output: 4.0
Justification: The subarray [3, -1, 10] has the highest average (3 + (-1) + 10) / 3 = 4.0.

Example 3

Input: nums = [-5, -2, 0, 3, 9, -1, 2], k = 4
Expected Output: 3.25
Justification: The subarray [3, 9, -1, 2] has the highest average (3 + 9 + (-1) + 2) / 4 = 3.25.

Constraints:

n == nums.length
1 <= k <= n <= 10⁵
-10⁴ <= nums[i] <= 10⁴

Pattern cue: fixed-size sliding window of width k — maximize the window sum (then divide by k for the average). Negatives are fine for fixed windows.

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Maximum Average Subarray I

1. Why / judgment

For fixed length k, average = sum/k and k is constant across candidates — so max average ≡ max window sum. Fixed window slides in O(1) per step; negatives are fine because width never shrinks on a monotonicity argument.

2. Worked sums + complexity (K11)

nums=[1,2,3,4,5,6], k=2
Pair averages: 1.5, 2.5, 3.5, 4.5, 5.5 → max 5.5
Running sums: seed sum=1+2=3; then +3−1=5; +4−2=7; +5−3=9; +6−4=11
  bestSum=11 → max avg = 11/2 = 5.5 ✓

n=7,k=3 page ex [0,1,1,3,-1,10,-2]:
  window sums: 2, 5, 3, 12, 7 → best 12; 12/3=4.0 ✓

Time: seed O(k) + slides O(n−k) → Θ(n); space Θ(1)
Brute each window rescan → Θ(n·k) worse when k large.

3. Pattern — FIXED-SIZE SLIDING WINDOW (K12)

Name: Fixed-k max sum (then /k).

Recognition: “contiguous length exactly k”, max/min average or sum.

When-NOT: variable length constraint → expand/shrink template; non-contiguous subset → different problem; need max of variable window extrema with removals → monotonic deque.

4. Edge hand-run (K13)

k=n: one window = total sum / n
k=1: answer = max element (handles negatives)
All negative: still max sum among windows (least negative avg)

5. Interviewer follow-ups

Q1. Why compare sums not averages each step?
A: Same k → argmax sum = argmax avg; fewer divisions; same comparisons.

Q2. Do negatives break fixed window?
A: No — fixed width does not rely on monotonic shrink.

Q3. Complexity?
A: Θ(n) time, Θ(1) space.

✅ Solution Maximum Average Subarray I

Problem Statement

Given an array of integers and an integer k, find a contiguous subarray of length k that has the highest average value, and return this maximum average value.

Examples

Example 1

Input: nums = [1, 2, 3, 4, 5, 6], k = 2
Expected Output: 5.5
Justification: The subarray [5, 6] has the highest average (5 + 6) / 2 = 5.5.

Example 2

Input: nums = [0, 1, 1, 3, -1, 10, -2], k = 3
Expected Output: 4.0
Justification: The subarray [3, -1, 10] has the highest average (3 + (-1) + 10) / 3 = 4.0.

Example 3

Input: nums = [-5, -2, 0, 3, 9, -1, 2], k = 4
Expected Output: 3.25
Justification: The subarray [3, 9, -1, 2] has the highest average (3 + 9 + (-1) + 2) / 4 = 3.25.

Constraints:

n == nums.length
1 <= k <= n <= 10⁵
-10⁴ <= nums[i] <= 10⁴

Pattern

Fixed-size sliding window. Recognition: every candidate is a contiguous block of exactly k elements; the score (here, average) is a reversible aggregate of the window (sum). Template: compute the sum of nums[0..k-1] once, then for each right endpoint i = k..n-1 do sum += nums[i] - nums[i-k] and track the max sum. Because average is sum/k and k is fixed, maximizing the sum is equivalent to maximizing the average — no floating-point work is needed until the final division.

When-not: if window size is variable ("at least k", "longest with property"), use expand/shrink variable window instead. If the aggregate is max/min (not sum), a plain running sum does not reverse on eviction — use a monotonic deque. Negatives are fine for fixed-size sum; they break only the variable-window shrink logic that relies on monotonic sums.

Complexity derivation: initial window = O(k) adds; each of the remaining n-k slides is O(1) add/subtract → total O(k) + O(n-k) = O(n) time, O(1) extra space.

Solution

To solve this problem, we need to find a subarray of length k with the highest average. We use a fixed-size sliding window: maintain a window of size k and slide it across the array, updating the sum by subtracting the element that leaves on the left and adding the element that enters on the right. One pass over the array is enough.

Compared with a nested-loop recompute of every window sum (O(n·k)), the incremental update reuses the previous sum, so total work is linear. Track the maximum sum, then divide by k once at the end.

Step-by-Step Algorithm

Initialize the sum of the first ( k ) elements and store it in a variable, say currentSum.
Initialize a variable maxSum with the value of currentSum.
Iterate through the array starting from the ( k )-th element to the end:
- For each element, update currentSum by adding the current element and subtracting the element that is ( k ) positions behind.
- Update maxSum if currentSum is greater than maxSum.
Return the maximum average by dividing maxSum by ( k ).

Algorithm Walkthrough

Step-by-Step Algorithm Walkthrough

Let's consider the example input nums = [-5, -2, 0, 3, 9, -1, 2], k = 4.

Initialization:
- Input array: [-5, -2, 0, 3, 9, -1, 2]
- Subarray length (k): 4
- Calculate the initial sum of the first k elements: sum([-5, -2, 0, 3]) = -5 + (-2) + 0 + 3 = -4
- Set maxSum to this initial sum: maxSum = -4
- Initialize currentSum to maxSum: currentSum = -4
Sliding Window:
- Start sliding the window from the k-th element (index 4) to the end of the array.
- First Slide (i = 4):
  - Add the next element nums[4] = 9 and remove the first element of the previous window nums[0] = -5:
    - currentSum = currentSum + nums[4] - nums[0] = -4 + 9 - (-5) = 10
  - Update maxSum if currentSum is greater:
    - maxSum = max(maxSum, currentSum) = max(-4, 10) = 10
- Second Slide (i = 5):
  - Add the next element nums[5] = -1 and remove the first element of the previous window nums[1] = -2:
    - currentSum = currentSum + nums[5] - nums[1] = 10 + (-1) - (-2) = 11
  - Update maxSum if currentSum is greater:
    - maxSum = max(maxSum, currentSum) = max(10, 11) = 11
- Third Slide (i = 6):
  - Add the next element nums[6] = 2 and remove the first element of the previous window nums[2] = 0:
    - currentSum = currentSum + nums[6] - nums[2] = 11 + 2 - 0 = 13
  - Update maxSum if currentSum is greater:
    - maxSum = max(maxSum, currentSum) = max(11, 13) = 13
Calculate the Maximum Average:
- The final maximum sum of any subarray of length k is maxSum = 13.
- The maximum average is maxSum / k = 13 / 4 = 3.25.

Code

java

class Solution {

  public double findMaxAverage(int[] nums, int k) {
    int n = nums.length;
    double maxSum = 0;

    // Compute the sum of the first 'k' elements
    for (int i = 0; i < k; i++) {
      maxSum += nums[i];
    }

    double currentSum = maxSum;

    // Slide the window across the array
    for (int i = k; i < n; i++) {
      currentSum += nums[i] - nums[i - k];
      maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum / k;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    int[] nums1 = { 1, 2, 3, 4, 5, 6 };
    int k1 = 2;
    System.out.println(
      "Expected: 5.5, Output: " + solution.findMaxAverage(nums1, k1)
    );

    // Example 2
    int[] nums2 = { 0, 1, 1, 3, -1, 10, -2 };
    int k2 = 3;
    System.out.println(
      "Expected: 4.0, Output: " + solution.findMaxAverage(nums2, k2)
    );

    // Example 3
    int[] nums3 = { -5, -2, 0, 3, 9, -1, 2 };
    int k3 = 4;
    System.out.println(
      "Expected: 3.25, Output: " + solution.findMaxAverage(nums3, k3)
    );
  }
}

Complexity Analysis

Time Complexity: The algorithm iterates through the array once, making it , where n is the number of elements in the array. This is efficient because it only requires a single pass to compute the sum of the subarrays.
Space Complexity: The space complexity is because we are using a fixed amount of extra space regardless of the input size.

🎯 STRICT STANDOUT: Why / complexity derivation / pattern+when-not / edges / drills — Solution Maximum Average Subarray I

Why this exists (judgment layer)

Fixed-size window is the first sliding-window form: O(n) after O(k) init by incremental sum. Average = sum/k so max average ≡ max sum when k fixed.

Worked example & complexity derivation

nums=[-5,-2,0,3,9,-1,2], k=4
init sum[-5,-2,0,3]=-4; maxSum=-4
i=4: -4+9-(-5)=10; max=10  window[-2,0,3,9]
i=5: 10+(-1)-(-2)=11; max=11 window[0,3,9,-1]
i=6: 11+2-0=13; max=13 window[3,9,-1,2]
avg=13/4=3.25
Derivation: O(k)+O(n-k)=O(n) time, O(1) space
Naive recompute each window: O((n-k+1)·k)=O(nk)

Pattern transfer & when-NOT

Pattern: FIXED-SIZE SLIDING WINDOW with reversible aggregate (sum). When-NOT: variable length ('at least k', 'longest with property') → expand/shrink; aggregate max/min → monotonic deque (sum does not reverse for max). Negatives are fine for fixed sum; they break variable shrink that assumes positive adds.

Edge cases (hand-run)

k=n → one window, answer = total/n. k=1 → max element. All negative → least-negative window sum (still max). Constraints: 1≤k≤n.

Hostile-panel drills (defend the decision)

Q1. Why maximize sum instead of average each step?
Model answer: k constant ⇒ avg = sum/k monotone in sum; avoid float until final division.

Q2. What breaks if the problem becomes 'max average of length ≥ k'?
Model answer: Fixed window fails; need different techniques (binary search on average + prefix, etc.).

Q3. Hand-run [1,2,3,4,5,6] k=2.
Model answer: Windows sums 3,5,7,9,11 → max 11 → avg 5.5 from [5,6].

🧩 Pattern · Sliding Window

Recognize it: Best/longest/count over a contiguous subarray or substring → grow the window, shrink it when a constraint breaks.

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Maximum Average Subarray I? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Maximum Average Subarray I** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Maximum Average Subarray I** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Maximum Average Subarray I**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Maximum Average Subarray I**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Sliding Window — Fixed vs Variable Maximum Number of Vowels in a Subs →