Maximum Average Subarray I

EasySliding Window · Fixed Size🧩 Sliding Window LeetCode #643 ↗Updated Oct 30, 2026

Problem

Given an integer array nums and a window length k, look at every contiguous block of exactly k elements and return the largest average among them. Answers within 10^-5 of the true value are accepted.

Inputnums = [1,12,-5,-6,50,3], k = 4Output12.75 (block [12,-5,-6,50])

Inputnums = [5], k = 1Output5.0

1 ≤ k ≤ n ≤ 10⁵ · -10⁴ ≤ nums[i] ≤ 10⁴

Try it yourself

Java

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

All windows have the same length k, so maximising the average is the same as maximising the sum. Neighbouring windows share k - 1 elements: add the newcomer, subtract the one that falls off.

PatternSliding Window

Instinct Longest, shortest or count of contiguous subarrays/substrings meeting a rule? Grow a window on the right, shrink it on the left, never step back.

Memory hack Move like a caterpillar - the head stretches forward to grab, the tail pulls up only when the body breaks the rule.

Open the Sliding Window guide →

Approaches

Brute ForceSum Every Window

Time O(n · k)Space O(1)

For each start i from 0 to n - k, add up the k elements from scratch and keep the biggest total. Divide by k once at the end.

Java

public double findMaxAverage(int[] nums, int k) {
    int best = Integer.MIN_VALUE;
    for (int i = 0; i + k <= nums.length; i++) {
        int sum = 0;
        for (int j = i; j < i + k; j++) sum += nums[j];
        best = Math.max(best, sum);
    }
    return (double) best / k;
}

Direct, but recomputes overlapping sums — O(n·k) blows up when k ≈ n/2.

BetterPrefix Sums

Time O(n)Space O(n)

Precompute pre[i] = sum of the first i elements. The sum of the window starting at i is then pre[i + k] - pre[i], available in O(1).

Java

public double findMaxAverage(int[] nums, int k) {
    int n = nums.length;
    long[] pre = new long[n + 1];
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
    long best = Long.MIN_VALUE;
    for (int i = 0; i + k <= n; i++) {
        best = Math.max(best, pre[i + k] - pre[i]);
    }
    return (double) best / k;
}

Linear time, but stores an extra array the problem doesn't need.

OptimalFixed-Size Sliding Window

Time O(n)Space O(1)

Sum the first k elements once. Then slide one step at a time: sum += nums[i] - nums[i - k]. Every window sum costs O(1) and only one running total is kept.

Java

public double findMaxAverage(int[] nums, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) sum += nums[i];
    int best = sum;
    for (int i = k; i < nums.length; i++) {
        sum += nums[i] - nums[i - k]; // add newcomer, drop oldest
        best = Math.max(best, sum);
    }
    return (double) best / k;
}

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

o droppedn added changed

init
1

12

-5

-6

50

3

sum 2, best 2
i=4
1
o
12

-5

-6

50
n
3

2+50-1=51, best 51
i=5
1

12
o
-5

-6

50

3
n
51+3-12=42
end
1

12

-5

-6

50

3

51 / 4 = 12.75 ✔

Single pass, constant memory — the textbook fixed window.

Pro tip

Compare integer sums and divide only once at the end — no repeated floating-point rounding.

At a glance

Level	Approach	Time	Space
Brute Force	Sum Every Window	`O(n · k)`	`O(1)`
Better	Prefix Sums	`O(n)`	`O(n)`
Optimal	Fixed-Size Sliding Window	`O(n)`	`O(1)`

Common pitfalls

Starting best at 0 — wrong when every number is negative.
Integer division: cast to double before dividing by k.
Off-by-one on the last window: the final start index is n - k.

Interview tips

Note that equal window sizes let you compare sums instead of averages.
Check overflow: |sum| ≤ 10⁵ · 10⁴ = 10⁹ fits in an int.
Name it a fixed-size window to contrast with variable windows.

Pattern

Fixed-size sliding window → aggregate (sum/count) over every block of exactly k consecutive elements.

My notes saved in this browser