LeetCode · #643

Maximum Average Subarray I Solution

Given an integer array nums and an integer k, return the maximum average value of any contiguous subarray of length k.

Section One · Problem

Problem Statement

🏷️

Difficulty

Easy

🔗

LeetCode

Problem #643

🏗️

Pattern

Sliding Window — fixed size

We need the contiguous subarray of exactly k elements whose average is largest. Because every candidate window has the same size, maximizing the average is the same as maximizing the sum. That makes this a classic fixed-size sliding window problem.

Example 1

 Input: nums = [1, 12, -5, -6, 50, 3], k = 4 Output: 12.75 // Best window is [12, -5, -6, 50] with sum 51 → average 51 / 4 = 12.75 

Example 2

 Input: nums = [5], k = 1 Output: 5.0 

Constraints

 • 1 ≤ k ≤ nums.length ≤ 10⁵ • -10⁴ ≤ nums[i] ≤ 10⁴ • Any answer within 10⁻⁵ of the actual answer is accepted 

Section Two · Approach 1

Brute Force — Recompute Every Window

Try every window of length k. For each start index, sum the next k elements from scratch, compute its average, and track the best.

Problem: Adjacent windows overlap heavily. If window [i, i+k-1] is already known, then window [i+1, i+k] differs by only one outgoing and one incoming element. Recomputing all k numbers wastes work and leads to O(n·k).

Java — Re-sum each window

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

Python — Re-sum each window

 class Solution:
def findMaxAverage(self, nums: list[int], k: int) -> float:
        best = float('-inf')
for start in range(len(nums) - k + 1):
            window_sum = 0 for i in range(start, start + k):
                window_sum += nums[i]
            best = max(best, window_sum / k)
return best

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

Section Three · Approach 2

Fixed-Size Sliding Window — O(n)

Build the first window sum of size k. Then slide right one step at a time: add the new number entering the window and subtract the old number leaving it. Track the maximum window sum seen. Because k is fixed, the best average comes from the best sum.

💡 Mental model: Imagine a tray that always holds exactly k cups of water. When the tray moves one slot right, one cup falls off the left and one new cup is added on the right. You do not re-measure every cup on the tray — you just subtract the old one and add the new one.

Algorithm

Step 1: Sum the first k elements.
Step 2: Set bestSum = windowSum.
Step 3: For each next position: windowSum += nums[right] - nums[right-k].
Step 4: Update bestSum after each slide.
Step 5: Return (double) bestSum / k.

🎯 Key insight:

Because every window has the same size, you never need to compare averages during the scan. Comparing sums is enough.
Divide by k only once at the end.

Section Four · Trace

Visual Walkthrough

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

Slide a fixed window of size 4

Section Five · Implementation

Code — Java & Python

Java — Fixed sliding window

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

Python — Fixed sliding window

 class Solution:
def findMaxAverage(self, nums: list[int], k: int) -> float:
        window_sum = sum(nums[:k])
        best_sum = window_sum
for right in range(k, len(nums)):
            window_sum += nums[right] - nums[right - k]
            best_sum = max(best_sum, window_sum)
return best_sum / k

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Recompute each window	O(n · k)	O(1)	Simple but repeats overlapping work
Sliding window ← optimal	O(n)	O(1)	Each slide updates sum in O(1)

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
k = 1	`[4, -2, 9], k=1`	Answer is just the maximum single element → 9.
k = n	`[2, 3, 4], k=3`	Only one possible window — average of whole array.
All negative	`[-5, -2, -8], k=2`	Best answer can still be negative. Don't initialize best to 0.
Single element	`[5], k=1`	Trivial fixed window.
Large values	`[10000, ...]`	Use a wide enough sum type in Java to stay safe.

⚠ Common Mistake: Doing integer division in Java. If you return bestSum / k as integers, decimals are truncated. Cast before dividing: (double) bestSum / k.

← Back to Sliding Window problems

LearningTree

LC 643 · Maximum Average Subarray I — Solution & Explanation | DSA Guide