Find the Maximum Average Subarray (Sliding Window) - Java

Category: Medium | Concepts used: Sliding window technique

---

Problem Statement

Given an array and a window size K, find the contiguous subarray of length K with the maximum average.

Input : [1, 12, -5, -6, 50, 3], K=4      Output: 12.75   (subarray [12,-5,-6,50] -> sum=51, avg=12.75)

Examples (with edge scenarios)

#	Input	K	Output	Why
1	[1,12,-5,-6,50,3]	4	12.75	Window [12,-5,-6,50] has the highest average
2	[5]	1	5.0	Single-element window — average is the element itself
3	[1,2,3]	3 (K == length)	2.0	Only one possible window: the whole array
4	[-1,-2,-3] (all negative)	1	-1.0	Best window is the single least-negative element
5	[1,2]	5 (K > length)	Invalid input — needs clarification	K cannot exceed array length

Common Fresher Mistake

Mistake	What happens	Fix
Recomputing the full sum of each window from scratch in a loop	Works, but O(n*K) — wasteful, since consecutive windows share most of their elements	Use a sliding window: slide by removing the element leaving the window and adding the element entering it
Not validating K against the array length	May cause index-out-of-bounds errors	Check K <= arr.length before proceeding

---

Before You Code: Clarify the Contract

Before choosing an algorithm, confirm whether the array may be null or empty, whether duplicates and original order matter, whether the method may modify the input, and whether the answer should contain values or original indices. These choices can change both the code and the best data structure.

Analogy: Passengers on a Moving Train

Imagine a train with exactly K cars (the sliding window) moving along a train track where each stop has a passenger count (the elements of the array):

• Solution 1 (Brute Force): At every stop, you completely empty the train and count all passengers one-by-one starting from car 1 to car K. When the train moves to the next stop, you repeat this entire process. This is exhausting and wastes time.
• Solution 2 (Sliding Window): You simply count the passengers inside the train once at the start.
  • When the train moves forward one stop, one passenger exits the train from the very last car (arr[i-k]), and one new passenger enters the train from the very front car (arr[i]).
  • To find the new passenger count, you just take the old count, subtract the person who exited (- arr[i-k]), and add the person who entered (+ arr[i]).
  • You do this instantly in one step without ever having to count the people sitting in the middle cars again!

---

Solution 1 — Brute Force (Recompute Sum for Every Window)

Intuition

For every possible starting position of a K-length window, add up all K elements from scratch, then compare that window’s average to the best one seen so far.

public class MaxAvgBruteForce {
    public static double findMaxAverage(int[] arr, int k) {
        double maxAvg = Double.NEGATIVE_INFINITY;

for (int i = 0; i <= arr.length - k; i++) {
            double sum = 0;
            for (int j = i; j < i + k; j++) {
                sum += arr[j]; // recompute the whole window sum from scratch
            }
            maxAvg = Math.max(maxAvg, sum / k);
        }
        return maxAvg;
    }

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

Output:

12.75

Dry Run (arr=[1,12,-5,-6], k=4 — just the first window for brevity)

i=0: sum = 1+12+(-5)+(-6) = 2, avg = 2/4 = 0.5
maxAvg so far = 0.5
(continues checking further windows...)

Interviewer’s take

Correct, but wasteful — recomputing each window’s sum from scratch is O(n*K), when consecutive windows actually overlap heavily and share almost all their elements. Interviewers will push for the sliding window optimization.

Follow-up questions you might get:

• “Notice how much these windows overlap — can you avoid redoing all that work?” → leads to Solution 2.

---

Solution 2 — Sliding Window (O(n), Recommended)

Intuition

Consecutive windows differ by just one element on each end — the window “slides” by dropping its leftmost element and picking up one new element on the right. So instead of recomputing the whole sum, just take the previous window’s sum, subtract the element that’s leaving, and add the element that’s entering — like adjusting a running total instead of recounting everything each time.

public class MaxAvgSlidingWindow {
    public static double findMaxAverage(int[] arr, int k) {
        // compute the sum of the FIRST window directly
        double windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }

double maxSum = windowSum;

// slide the window: remove the outgoing element, add the incoming one
        for (int i = k; i < arr.length; i++) {
            windowSum += arr[i] - arr[i - k]; // add new, remove old
            maxSum = Math.max(maxSum, windowSum);
        }

return maxSum / k;
    }

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

Output:

12.75

Dry Run (arr=[1,12,-5,-6,50,3], k=4)

First window (indices 0-3): windowSum = 1+12-5-6 = 2
maxSum = 2

Slide to i=4 (arr[4]=50, removing arr[0]=1):
windowSum = 2 + (50 - 1) = 51
maxSum = max(2, 51) = 51

Slide to i=5 (arr[5]=3, removing arr[1]=12):
windowSum = 51 + (3 - 12) = 42
maxSum = max(51, 42) = 51

Final: maxSum=51, avg = 51/4 = 12.75

Interviewer’s take

This is the preferred, optimal answer — O(n) time instead of O(n*K), by reusing the previous window’s sum instead of recalculating from scratch. The sliding window pattern shown here (subtract outgoing, add incoming) is one of the most reused techniques across array/string problems — very valuable to have solid.

Follow-up questions you might get:

• “Why is arr[i] - arr[i-k] the right adjustment?” → As the window slides forward by one position, it gains the new element at index i and loses the element that’s now k positions behind it (i-k) — everything else in between stays exactly the same, so only these two elements need adjusting.
• “What if K equals the array length?” → The loop for sliding never executes (since there’s only one possible window), and the answer is just the whole array’s average — correctly handled without special-casing.

---

📊 Visual Flowchart

graph TD
    Start["Input: Array arr, window size K"] --> Init["sum = sum(arr[0] to arr[K-1])<br>maxSum = sum<br>i = K"]
    Init --> Loop{"i < arr.length?"}
    Loop -->|Yes| Slide["sum = sum + arr[i] - arr[i-K]"]
    Slide --> UpdateMax["maxSum = max(maxSum, sum)"]
    UpdateMax --> Next["i++"]
    Next --> Loop
    Loop -->|No| CalcAvg["avg = maxSum / K"]
    CalcAvg --> End["Return avg"]

---

Final Verdict — Which Solution Should You Give?

• Solution 2 (sliding window) is the expected final answer — this is a textbook example specifically used to teach and test the sliding window pattern.

---

Quick Recap

Approach	Time	Space	Interview Signal
Brute force (recompute each window)	O(n·K)	O(1)	Correct, but not optimal
Sliding window	O(n)	O(1)	Preferred, shows key pattern