Sliding Window Maximum Average Subarray in Java DSA

Solve Sliding Window Maximum Average Subarray in Java DSA in three ways — brute force, prefix sum, and sliding window — with full step-by-step dry runs and clean code.

1. Introduction

The Sliding Window pattern is one of the most useful tricks for array problems, and Maximum Average Subarray I in Java is the perfect place to learn it. The problem is small. You get an array of numbers and a window size k. Your job is to find the block of k numbers in a row that has the highest average.

So if the array is [1, 12, -5, -6, 50, 3, 30] and k is 4, you look at every group of 4 numbers next to each other. Then you pick the group with the biggest average and return that number.

There is one small thing to notice. The average of a fixed group is just its sum divided by k. Since k never changes, the group with the biggest sum also has the biggest average. So we can chase the biggest sum and divide once at the end.

We will build the answer in three steps, like always. The brute force recomputes each window sum from scratch. The prefix sum trick makes each window sum a quick subtraction. Then the sliding window slides one window across the array and reuses the old sum.

Every approach gets a full, step-by-step dry run on the same seven numbers. Nothing is skipped, so you can watch the sum change at each move and see exactly why one window wins.

2. Understanding the Problem

Let us pin down the rules before we write any code.

• You get an integer array nums and a number k.
• A subarray means numbers that sit next to each other, with no gaps.
• You must pick a subarray that is exactly k numbers long.
• Return the highest average you can get from any such window.

For our array [1, 12, -5, -6, 50, 3, 30] with k = 4, the best window is [-6, 50, 3, 30]. Its sum is 77, so its average is 77 divided by 4, which is 19.25. No other window of length 4 beats that.

3. Concepts You Need Here

3.1 A Fixed Window Means Sum Is Enough

Every window here has the same length k. So dividing by k treats all windows the same way. Because of that, the window with the largest sum is also the window with the largest average.

• Track the biggest sum while you scan.
• Divide that best sum by k only once, right at the end.

3.2 Reusing Work Instead of Repeating It

The slow way finds each window sum on its own, adding k numbers every time. Notice that two windows next to each other share most of their numbers. So instead of adding everything again, you can drop the number that left and add the number that entered.

• One number slides out on the left as the window moves.
• One number slides in on the right at the same time.

4. Approach 1: Brute Force Window Sums

Try every starting spot for the window. For each start, add up the k numbers in that window from scratch. Keep the biggest sum you have seen. It is the plainest idea, and it works, but it redoes a lot of adding.

4.1 Pseudocode

best = negative infinity

for start = 0 to n - k:
    windowSum = 0
    for j = start to start + k - 1:
        windowSum = windowSum + nums[j]
    if windowSum > best:
        best = windowSum

return best / k

4.2 Pseudocode Explained

The plan is simple. Look at every window, add its numbers, and remember the largest sum.

• The outer loop picks where the window starts. It stops at n minus k, since a window past that point would run off the end.
• The inner loop adds the k numbers of the current window into windowSum.
• After each window, we compare its sum with best and keep the larger one.
• Finally we divide the best sum by k to turn it into an average.

4.3 Java Code

public class MaxAverageBrute {

    public static double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        double best = Double.NEGATIVE_INFINITY;
        for (int start = 0; start <= n - k; start++) {
            int windowSum = 0;
            for (int j = start; j < start + k; j++) {
                windowSum += nums[j];
            }
            if (windowSum > best) {
                best = windowSum;
            }
        }
        return best / k;
    }

    public static void main(String[] args) {
        int[] nums = {1, 12, -5, -6, 50, 3, 30};
        System.out.println(findMaxAverage(nums, 4)); // 19.25
    }
}

4.4 Java Code Explained

This is the same plan, written in Java. We start best very low so the first window always wins the first compare.

• Line 5 sets best to negative infinity, a safe floor below any real sum.
• Line 6 is the outer loop. It moves the window start from 0 up to n minus k.
• Next, lines 7 to 10 reset windowSum to 0 and add the k numbers of this window.
• Then lines 11 to 13 keep best as the larger of best and the new windowSum.
• Line 15 divides best by k once, which turns the biggest sum into the answer.

4.5 Dry Run of the Brute Force

Let us trace nums = [1, 12, -5, -6, 50, 3, 30] with k = 4. The array has 7 numbers, so a window of size 4 can start at index 0, 1, 2, or 3. That gives us four windows to check. best begins at negative infinity.

This table shows each window, the numbers inside it, the fresh sum we add up, and whether it beats best.

After all four windows, best holds 77. We divide by k, so 77 divided by 4 gives 19.25. That is the answer.

4.6 Reading the Dry Run

Let us walk each window and see exactly what the brute force does at every start.

start = 0, window [1, 12, -5, -6].

The inner loop begins fresh and adds all four numbers of this first window.

• It adds 1, then 12, giving a running total of 13.
• Next it adds -5, which pulls the total down to 8.
• Then it adds -6, so the window sum lands at 2.

best was negative infinity, so 2 easily beats it. Now best is 2.

start = 1, window [12, -5, -6, 50].

The window shifts right by one, and the inner loop adds all four numbers again from scratch.

• It adds 12 and -5 to reach 7, then adds -6 to drop to 1.
• After that it adds 50, which shoots the total up to 51.
• Because 51 is bigger than the old best of 2, best jumps to 51.

Notice the waste here. We added -5 and -6 in the last window too, yet we added them again.

start = 2, window [-5, -6, 50, 3].

Again the inner loop adds all four fresh numbers of this window.

• It adds -5 and -6 first, so the total sinks to -11.
• Then it adds 50 to climb back to 39, and adds 3 to reach 42.
• Since 42 is smaller than best of 51, best does not change.

This window looked promising thanks to the 50, but the two negatives at the front held it back.

start = 3, window [-6, 50, 3, 30].

This is the last window, since start cannot go past index 3 here.

• It adds -6 and 50 to reach 44, then adds 3 to get 47.
• Finally it adds 30, which lifts the sum to 77.
• As 77 beats the best of 51, best updates to 77.

This window drops the deep negatives from earlier and keeps three strong numbers, so it wins. After the loop ends, best is 77 and the average is 19.25.

Interview Insight A common opener is “what is the time cost of the plain version?” Say O(n times k). You scan n windows and re-add k numbers for each one, which is wasteful when the same numbers keep repeating.

4.7 Time and Space Cost

• Time is O(n times k), since each of the windows re-adds k numbers.
• Space is O(1), because we only keep a couple of number variables.

The result is correct, but the repeated adding hurts on long arrays. Next we cut that repeated work with a prefix sum.

5. Approach 2: Prefix Sum

Build a prefix array first. Slot i of the prefix holds the sum of all numbers before index i. Once you have it, any window sum becomes one subtraction. The sum from start to start plus k is just prefix[start + k] minus prefix[start].

5.1 Pseudocode

prefix = array of size n + 1, all zeros

for i = 0 to n - 1:
    prefix[i + 1] = prefix[i] + nums[i]

best = negative infinity
for start = 0 to n - k:
    windowSum = prefix[start + k] - prefix[start]
    if windowSum > best:
        best = windowSum

return best / k

5.2 Pseudocode Explained

Think of prefix as a running total that never resets. Each slot stores the total up to that point.

• The first loop fills prefix, where prefix[i + 1] is the sum of the first i + 1 numbers.
• Any window sum is then the big running total minus the part before the window.
• So windowSum for a start is prefix[start + k] minus prefix[start], done in one step.
• We track the largest windowSum and divide it by k at the end.

5.3 Java Code

public class MaxAveragePrefix {

    public static double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        double best = Double.NEGATIVE_INFINITY;
        for (int start = 0; start <= n - k; start++) {
            long windowSum = prefix[start + k] - prefix[start];
            if (windowSum > best) {
                best = windowSum;
            }
        }
        return best / k;
    }

    public static void main(String[] args) {
        int[] nums = {1, 12, -5, -6, 50, 3, 30};
        System.out.println(findMaxAverage(nums, 4)); // 19.25
    }
}

5.4 Java Code Explained

The Java version follows the same two loops. We use long for prefix so big arrays do not overflow.

• Line 5 makes the prefix array of size n plus 1, with an extra 0 at the front.
• Lines 6 to 8 fill it, so each prefix[i + 1] adds the next number to the running total.
• Then line 10 starts best at negative infinity, our safe floor.
• Lines 11 to 15 get each window sum by one subtraction and keep the largest one.
• Line 17 divides best by k, which gives the final average.

5.5 Dry Run of the Prefix Sum

Same input, nums = [1, 12, -5, -6, 50, 3, 30] and k = 4. First we build the prefix array. It has 8 slots, since n is 7. Slot 0 stays at 0, and each next slot adds one more number.

This first table builds prefix one number at a time.

So the finished prefix array is [0, 1, 13, 8, 2, 52, 55, 85]. Now each window sum is just one subtraction. best starts at negative infinity.

This second table finds each window sum by subtracting two prefix slots.

best ends at 77, so the average is 77 divided by 4, which is 19.25. Same answer as before, but each window took one subtraction instead of four additions.

5.6 Reading the Dry Run

Let us split this into the build pass and the query pass.

Building the prefix array.

This pass just keeps a running total and stores it after each number.

• Slot 0 stays 0, which stands for the sum before any number.
• At i = 0 we add 1, so prefix[1] becomes 1. Then at i = 1 we add 12, so prefix[2] becomes 13.
• Next at i = 2 the -5 pulls it to 8, and at i = 3 the -6 pulls it to 2.
• During i = 4 the 50 lifts it to 52, and at i = 5 the 3 makes 55, and at i = 6 the 30 makes 85.

Now prefix holds the total up to every point, which is all we need for fast window sums.

Querying each window.

Each window sum is the running total at its end minus the running total at its start.

• For start 0, prefix[4] minus prefix[0] is 2 minus 0, so the sum is 2, and best becomes 2.
• At start 1, prefix[5] minus prefix[1] is 52 minus 1, which is 51, so best jumps to 51.
• For start 2, prefix[6] minus prefix[2] is 55 minus 13, which is 42, so best stays 51.
• At start 3, prefix[7] minus prefix[3] is 85 minus 8, which is 77, so best rises to 77.

The subtraction works because the part before the window cancels out, leaving only the numbers inside it. best finishes at 77, so the average is 19.25.

Interview Insight If asked “why does prefix[start + k] minus prefix[start] give the window sum?”, explain that the first term is the total up to the window end, and the second is the total up to the window start. Subtracting removes everything before the window.

5.7 Time and Space Cost

• Time is O(n), since we build prefix once and then do one subtraction per window.
• Space is O(n), because the prefix array holds n plus 1 numbers.

This is much faster than brute force. Still, it needs an extra array. The sliding window gets the same speed while using almost no extra space.

6. Approach 3: Sliding Window

Add the first k numbers to get the first window sum. Then slide the window one step at a time. At each step, add the number that enters on the right and subtract the number that leaves on the left. Track the biggest sum as you go. No extra array, and each number is touched about once.

6.1 Pseudocode

windowSum = 0
for i = 0 to k - 1:
    windowSum = windowSum + nums[i]

best = windowSum
for i = k to n - 1:
    windowSum = windowSum + nums[i] - nums[i - k]
    if windowSum > best:
        best = windowSum

return best / k

6.2 Pseudocode Explained

Picture a frame exactly k boxes wide sitting over the array. The whole trick is that when the frame moves one step, only the two edge boxes change. Everything in the middle stays put, so we never re-add it. Let us read the pseudocode in three small phases.

Phase 1: build the first window.

The first loop fills windowSum with the first k numbers. This is the only time we add k numbers the slow way. After it, windowSum holds the sum of the window that sits at the very start of the array.

• windowSum starts at 0, an empty running total.
• The loop runs from index 0 up to k minus 1, so it covers exactly the first k numbers.
• Each pass does windowSum = windowSum + nums[i], adding one more number to the total.

Phase 2: seed the best value.

Right after building, we set best to windowSum. We have only seen one window so far, so that window is the best by default. There is no comparison to make yet.

• best now holds the first window sum, ready to be challenged by later windows.

Phase 3: slide and update.

The second loop is where the real work happens, and it is short. Here index i points at the number entering on the right. Meanwhile the number leaving on the left always sits k spots behind it, at index i minus k.

• The loop starts at i = k, because index k is the first number that is not already inside the window.
• The core line is windowSum = windowSum + nums[i] – nums[i – k]. It adds the entering number and drops the leaving number in one move.
• So the whole window shifts right by one, but we only changed two numbers, not k of them.
• Then we compare windowSum with best and keep whichever is larger.
• Once the loop ends, best holds the largest window sum, and we divide it by k to get the average.

6.3 Java Code

public class MaxAverageSliding {

    public static double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        long windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += nums[i];
        }
        long best = windowSum;
        for (int i = k; i < n; i++) {
            windowSum += nums[i] - nums[i - k];
            if (windowSum > best) {
                best = windowSum;
            }
        }
        return (double) best / k;
    }

    public static void main(String[] args) {
        int[] nums = {1, 12, -5, -6, 50, 3, 30};
        System.out.println(findMaxAverage(nums, 4)); // 19.25
    }
}

6.4 Java Code Explained

The Java code has two short loops and no extra array. The one trick is the index i minus k, which points at the number leaving on the left.

• Lines 6 to 8 add the first k numbers into windowSum, forming window one.
• Then line 9 sets best to that first window sum.
• Line 10 starts the slide loop at index k, the first number that enters from the right.
• Line 11 adds nums[i] and removes nums[i – k], which slides the window by one.
• Lines 12 to 14 keep the largest sum, and line 16 divides by k for the average.

6.5 Dry Run of the Sliding Window

Same input again, nums = [1, 12, -5, -6, 50, 3, 30] and k = 4. First we build the starting window from the first four numbers. This table shows that build step by step.

So the first window [1, 12, -5, -6] has sum 2. We set best to 2. Now the slide begins at index 4. Each step adds nums[i] on the right and removes nums[i – k] on the left.

Legend: “enters” is nums[i], the new right number. “leaves” is nums[i – k], the old left number that slides out.

After the last slide, best is 77. We divide by k, so 77 divided by 4 is 19.25. Same answer, and we touched each number only about once.

6.6 Reading the Dry Run

Let us walk the whole run one move at a time. First we build the starting window, then we slide it three times. At every move, watch two things: which number enters, and which number leaves.

Building the first window (indexes 0 to 3).

This first loop is the only slow part, and it runs just once. It adds the first four numbers into windowSum, which starts empty at 0.

• At i = 0 it adds nums[0] = 1, so windowSum goes from 0 to 1.
• Moving to i = 1, it adds nums[1] = 12, so windowSum climbs from 1 to 13.
• At i = 2 the number is -5, which pulls windowSum down from 13 to 8.
• Then at i = 3 the number is -6, so windowSum drops from 8 to 2.

The starting window is [1, 12, -5, -6] and its sum is 2. This is the only window we have looked at, so best begins at 2. From here on, we never add four numbers again. Each slide changes only two.

Slide 1, at i = 4: 50 enters, 1 leaves.

The frame shifts right by one. It used to cover indexes 0 to 3, and now it covers indexes 1 to 4. So the new window is [12, -5, -6, 50].

• The entering number is nums[4] = 50, sitting on the right edge.
• The leaving number is nums[i – k] = nums[0] = 1, the old left edge.
• So the update is windowSum = 2 + 50 – 1, which gives 51.
• Because 51 is larger than the old best of 2, best jumps up to 51.

Notice what we did not do. We never re-added 12, -5, or -6, even though they are all inside the new window. They stayed inside the frame, so their contribution was already in windowSum. We only adjusted the two edges, and that is what makes each slide cheap.

Slide 2, at i = 5: 3 enters, 12 leaves.

The frame moves right again, now covering indexes 2 to 5. The window becomes [-5, -6, 50, 3].

• The entering number is nums[5] = 3 on the right edge.
• The leaving number is nums[i – k] = nums[1] = 12, which was the big number on the left.
• So the update is windowSum = 51 + 3 – 12, which gives 42.
• Since 42 is smaller than best of 51, best does not change and stays at 51.

This slide lost value. We dropped a strong 12 and only gained a small 3, so the window sum fell from 51 to 42. That is fine. We still keep best at 51, remembering the better window we saw earlier.

Slide 3, at i = 6: 30 enters, -5 leaves.

This is the final slide, since index 6 is the last spot in the array. The frame now covers indexes 3 to 6, so the window is [-6, 50, 3, 30].

• The entering number is nums[6] = 30 on the right edge.
• The leaving number is nums[i – k] = nums[2] = -5, a negative number on the left.
• Subtracting a negative actually adds, so windowSum = 42 + 30 – (-5) becomes 42 + 30 + 5, which is 77.
• As 77 beats best of 51, best updates to 77.

This slide gained twice over. It brought in a big 30 and, by dropping the -5, it removed a number that was dragging the sum down. Both changes push the sum up, so this window ends up the strongest of them all.

Wrapping up.

The loop is now done, and best holds 77. We divide by k, so 77 divided by 4 gives 19.25, which is the answer. Look back at the whole run: we added four numbers once at the start, then did just one add and one subtract per slide. That is why the sliding window is fast even when k is large.

Interview Insight Interviewers often ask “why is the slide O(1) per step?” Because each step only does one add and one subtract, no matter how large k is. The numbers already inside the window are never touched again.

6.7 Comparing the Three Traces

7. Comparing the Three Approaches

All three return the same answer, 19.25. They just pay different prices to get there.

Prefix sum and sliding window share the same linear time. What sets them apart is memory. The prefix version keeps a whole extra array, while the sliding window keeps just one running sum.

In an interview, mention brute force first to show you understand the problem. Then bring up prefix sum as a speed fix. Land on the sliding window as the clean answer, since it is fast and uses almost no extra space.

Interview Insight If pushed on the space claim, point out that the sliding window keeps only a running sum and a best value. That stays fixed no matter how long the array gets, so it counts as O(1) extra space.

8. Common Mistakes and Edge Cases

A few small traps catch beginners on this problem. Keep them in mind.

• Starting best at 0 breaks arrays with all negative numbers, so use a very low floor instead.
• Adding int values into an int sum can overflow on large inputs, so prefer long for the running sum.
• Dividing an int sum by an int k drops the decimals, so cast to double before dividing.
• When k equals the array length, there is exactly one window, which is the whole array.
• Forgetting to subtract the leaving number makes the window grow instead of slide.

Run a case with all negatives and a case where k equals the array length before you call it done. These catch more bugs than any normal input will.

9. Interview Questions

10. Conclusion

Maximum Average Subarray I in Java looks tiny, yet it teaches the sliding window habit you will reuse everywhere. Once you see a fixed window as one running sum, the whole problem clicks.

Our seven-number traces showed the payoff clearly. Brute force re-added every window from scratch. The prefix sum turned each window into one subtraction, and the sliding window reused the old sum with a single add and subtract.

So take the pattern, not just the answer. When a window has a fixed size, keep a running sum and fix only the two ends as it moves. Reach for prefix sum when you need many range sums, and reach for the sliding window when the window size stays the same.

That reuse habit turns many array problems from slow into quick. It will serve you well on the harder window problems waiting further down the list.

11. Further Reading

• LeetCode Maximum Average Subarray I problem — practice the original problem and submit your own solution.
• Oracle Java arrays tutorial — the official reference for the arrays used in every approach here.
• Previous in this series: Subarray Sum Equals K in Java — count subarrays that add up to a target using a prefix sum and a hash map.
• Next in this series: Best Time to Buy and Sell Stock II in Java — collect every upward move to get the maximum profit.