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⁴

Try it yourself

Try solving this question here:

✅ 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⁴

Solution

To solve this problem, we need to find a subarray of length ( k ) with the highest average. We can use a sliding window approach to efficiently calculate the sum of subarrays. By maintaining a window of size ( k ) and sliding it across the array, we can update the sum by subtracting the element that goes out of the window and adding the new element that enters the window. This approach ensures that we only need to pass through the array once, making it efficient in terms of time complexity.

The sliding window method is effective because it reduces the need for nested loops, which would result in higher time complexity. Instead, by adjusting the window's sum dynamically as it slides, we achieve the desired result in linear time. This makes our approach both time-efficient and easy to implement.

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.

🤖 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

← Introduction to Sliding Window Pat Maximum Number of Vowels in a Subs →