Maximum Average Subarray I

Find the maximum average among all contiguous subarrays of size k.

Open concept page Back to problem map

This is the cleanest fixed-size window starter problem.

It shows how a running sum turns a repeated range computation into linear work.

Problem intuition

The brute-force version recalculates each window sum from scratch.

The sliding-window version keeps the current sum and updates it by removing the outgoing number and adding the incoming one.

Java solution ladder

The solutions below are ordered from least optimal to most optimal, so you can see the improvement path instead of only the final answer.

Solution 1

Recompute each length-k sum

O(n * k)O(1)

For every start index, sum the whole length-k window again. Easy to write, but it repeats most of the same work.

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double best = -Double.MAX_VALUE;

        for (int start = 0; start <= nums.length - k; start++) {
            int sum = 0;

            for (int i = start; i < start + k; i++) {
                sum += nums[i];
            }

            best = Math.max(best, (double) sum / k);
        }

        return best;
    }
}

Solution 2

Fixed-size sliding window

O(n)O(1)

Compute the first window once, then update the sum in O(1) as the window slides forward.

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int windowSum = 0;

        for (int i = 0; i < k; i++) {
            windowSum += nums[i];
        }

        int best = windowSum;

        for (int right = k; right < nums.length; right++) {
            windowSum += nums[right];
            windowSum -= nums[right - k];
            best = Math.max(best, windowSum);
        }

        return (double) best / k;
    }
}