Maximum Average Subarray I (LC 643)

Pattern: Sliding Window - Fixed Size
Difficulty: Easy
Key Concept: Maintain a fixed window of size k, slide by adding/removing one element at a time

Problem Statement

Given an integer array nums and an integer k, find a contiguous subarray of length k that has the maximum average value. Return the maximum average.

• Input: int[] nums, int k
• Output: double (maximum average)

---

1. Algorithm & Pseudocode

FUNCTION findMaxAverage(nums, k):
    // Compute sum of first window
    windowSum = sum of nums[0..k-1]
    maxSum = windowSum
    
    // Slide the window
    FOR i = k TO nums.length - 1:
        windowSum = windowSum + nums[i] - nums[i - k]
        maxSum = max(maxSum, windowSum)
    
    RETURN maxSum / k

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Step 1: Calculate the sum of the first k elements. This is our initial window.
• Step 2: Slide the window one position at a time. Add the new element entering the window, subtract the element leaving.
• Step 3: Track the maximum window sum seen so far.
• Step 4: Divide by k at the end to get the average.
• Why not compute average each time? Division is expensive. Just track max sum and divide once.

---

3. The Dry Run

Input: nums = [1, 12, -5, -6, 50, 3], k = 4

Step	Window	windowSum	maxSum	Operation
Init	[1, 12, -5, -6]	2	2	Sum first 4
i=4	[12, -5, -6, 50]	2 + 50 - 1 = 51	51	Add 50, remove 1
i=5	[-5, -6, 50, 3]	51 + 3 - 12 = 42	51	Add 3, remove 12

Result: maxSum = 51, average = 51 / 4 = 12.75

---

4. Java Solution

Brute Force

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double maxAvg = Double.NEGATIVE_INFINITY;
        
        for (int i = 0; i <= nums.length - k; i++) {
            int sum = 0;
            for (int j = i; j < i + k; j++) {
                sum += nums[j];
            }
            maxAvg = Math.max(maxAvg, (double) sum / k);
        }
        
        return maxAvg;
    }
}

Optimal

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        long windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += nums[i];
        }
        
        long maxSum = windowSum;
        
        for (int i = k; i < nums.length; i++) {
            windowSum += nums[i] - nums[i - k];
            maxSum = Math.max(maxSum, windowSum);
        }
        
        return (double) maxSum / k;
    }
}

---

5. The “Java vs. Others” Edge

• long for sum: With n up to 10^5 and values up to 10^4, sum can reach 10^9 which fits in int. But using long is a safer habit to avoid overflow surprises.
• Double.NEGATIVE_INFINITY: Java’s way to initialize “smallest possible double.” In C++ use -DBL_MAX or numeric_limits<double>::lowest(). In Python use float('-inf').
• (double) sum / k: Without the cast, integer division truncates! 7 / 2 = 3 in Java. (double) 7 / 2 = 3.5. In Python 3, / always returns float.
• No sum() built-in: Java doesn’t have Arrays.sum() like Python’s sum(). You must loop or use IntStream.of(nums).sum().

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n * k)	O(1)	Recompute sum for each window
Sliding Window	O(n)	O(1)	Single pass, constant space