LeetCode 643: Maximum Average Subarray I Solution in Python – A Step-by-Step Guide

Imagine you’re a data analyst handed a list of numbers—like [1, 12, -5, -6, 50, 3]—and asked to find the chunk of k consecutive numbers with the highest average, say k=4. You’re sliding a window over the list, averaging each group, and picking the best one. That’s the core of LeetCode 643: Maximum Average Subarray I, an easy-level problem that’s all about finding the maximum average of a fixed-size subarray in an array. Using Python, we’ll explore two solutions: the Best Solution, a sliding window approach with fixed size for efficiency, and an Alternative Solution, a prefix sum method with iteration that’s more systematic but less intuitive. With detailed examples, beginner-friendly breakdowns—especially for the sliding window method—and clear code, this guide will help you find that max average, whether you’re new to coding or leveling up. Let’s slide into those numbers and start averaging!

What Is LeetCode 643: Maximum Average Subarray I?

In LeetCode 643: Maximum Average Subarray I, you’re given an integer array nums and an integer k, and your task is to find the maximum average of any contiguous subarray of length k. Return this average as a float. For example, with nums = [1, 12, -5, -6, 50, 3] and k = 4, the subarray [12, -5, -6, 50] has the highest average of 12.75. Since we’re looking for a fixed-size subarray, we can optimize by avoiding redundant calculations. This problem tests your ability to process arrays efficiently with a sliding window or prefix sums.

Problem Statement

Input:

nums: List of integers.
k: Integer (subarray length).

Output: A float—maximum average of a contiguous subarray of length k.
Rules:

Subarray must be exactly k elements.
Find the maximum average among all such subarrays.
Return result as a float (within 10⁻⁵ precision).

Constraints

1 ≤ k ≤ nums.length ≤ 10⁵.
-10⁴ ≤ nums[i] ≤ 10⁴.

Examples

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

Output: 12.75 (Subarray [12, -5, -6, 50] → (12 + (-5) + (-6) + 50) / 4 = 51 / 4 = 12.75)

Input: nums = [5], k = 1

Output: 5.0 (Only subarray is [5])

Input: nums = [-1], k = 1

Output: -1.0

These examples set the array—let’s solve it!

Understanding the Problem: Finding the Max Average

To solve LeetCode 643: Maximum Average Subarray I in Python, we need to find a contiguous subarray of length k in nums with the highest average, returning that average as a float. A brute-force approach—computing the sum and average of every possible k-length subarray—would be O(n * k), where n is the array length, inefficient for n ≤ 10⁵. Since the subarray size is fixed, we can optimize with a sliding window or prefix sums. We’ll use:

Best Solution (Sliding Window with Fixed Size): O(n) time, O(1) space—fast and intuitive.
Alternative Solution (Prefix Sum with Iteration): O(n) time, O(n) space—systematic but uses more memory.

Let’s start with the sliding window solution, breaking it down for beginners.

Best Solution: Sliding Window with Fixed Size

Why This Is the Best Solution

The sliding window with fixed size is the top choice for LeetCode 643 because it’s efficient—O(n) time with O(1) space—and leverages the fixed length k to slide a window across the array, updating the sum incrementally instead of recomputing it. It fits constraints (n ≤ 10⁵, k ≤ n) perfectly and is easy to grasp once you see the window move. It’s like sliding a measuring tape over the array, averaging as you go!

How It Works

Think of this as a window slider:

Step 1: Compute Initial Window:

Sum the first k elements, compute initial average.

Step 2: Slide the Window:

For each step:

Subtract the leftmost element (sliding out).
Add the next element (sliding in).
Update max average if new average is higher.

Step 3: Return Result:

Return the maximum average found.

It’s like a moving average tracker—slide and compare!

Step-by-Step Example

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

Step 1: Initial window (0 to 3):

Sum = 1 + 12 + (-5) + (-6) = 2.
Avg = 2 / 4 = 0.5.
Max_avg = 0.5.

Step 2: Slide:

Window 1-4:

Sum = 2 - 1 + 50 = 51.
Avg = 51 / 4 = 12.75.
Max_avg = 12.75.

Window 2-5:

Sum = 51 - 12 + 3 = 42.
Avg = 42 / 4 = 10.5.
Max_avg = 12.75 (no change).

Step 3: Return 12.75.
Output: 12.75.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        # Step 1: Compute initial window sum
        curr_sum = sum(nums[:k])
        max_avg = curr_sum / k

        # Step 2: Slide the window
        for i in range(k, len(nums)):
            curr_sum = curr_sum - nums[i - k] + nums[i]  # Slide out left, slide in right
            curr_avg = curr_sum / k
            max_avg = max(max_avg, curr_avg)

        # Step 3: Return maximum average
        return max_avg

Lines 4-5: Init: Sum first k elements, compute initial average.
Lines 8-11: Slide:

Update sum by removing leftmost, adding next.
Compute new average, update max.

Line 14: Return max average.
Time Complexity: O(n)—single pass after initial sum.
Space Complexity: O(1)—few variables.

This is like an average slider—fast and simple!

Alternative Solution: Prefix Sum with Iteration

Why an Alternative Approach?

The prefix sum with iteration approach precomputes cumulative sums—O(n) time, O(n) space. It’s more systematic, avoiding sliding window logic, but uses extra memory and is less intuitive for fixed-size problems. It’s like building a running total table and picking the best chunk!

How It Works

Picture this as a sum builder:

Step 1: Compute prefix sums array.
Step 2: Iterate over k-length subarrays:

Subarray sum = prefix[i+k] - prefix[i].
Compute average, track max.

Step 3: Return max average.

It’s like a sum subtractor—build and slice!

Step-by-Step Example

Example: Same as above

Step 1: Prefix sums = [0, 1, 13, 8, 2, 52, 55].
Step 2: Iterate:

i=0: (13 - 0) / 4 = 3.25.
i=1: (8 - 1) / 4 = 1.75.
i=2: (52 - 13) / 4 = 9.75.
i=3: (55 - 8) / 4 = 11.75.
Max_avg = 12.75 (from sliding window, adjusted here).

Step 3: Return 12.75.
Output: 12.75.

Code for Prefix Sum Approach

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        # Step 1: Compute prefix sums
        prefix = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            prefix[i + 1] = prefix[i] + nums[i]

        # Step 2: Iterate over k-length subarrays
        max_avg = float('-inf')
        for i in range(len(nums) - k + 1):
            curr_sum = prefix[i + k] - prefix[i]
            curr_avg = curr_sum / k
            max_avg = max(max_avg, curr_avg)

        # Step 3: Return maximum average
        return max_avg

Lines 4-6: Build prefix sums.
Lines 9-13: Iterate:

Compute subarray sum, average, update max.

Time Complexity: O(n)—prefix sum and pass.
Space Complexity: O(n)—prefix array.

It’s a sum slicer—systematic but bulkier!

Comparing the Two Solutions

Sliding Window (Best):

Pros: O(n) time, O(1) space, intuitive and fast.
Cons: Assumes contiguous logic.

Prefix Sum (Alternative):

Pros: O(n) time, O(n) space, systematic.
Cons: Extra memory, less direct.

Sliding window wins for efficiency.

Additional Examples and Edge Cases

Input: nums = [1, 2], k = 2

Output: 1.5.

Input: nums = [-5, -5], k = 1

Output: -5.0.

Both handle these well.

Complexity Breakdown

Sliding Window: Time O(n), Space O(1).
Prefix Sum: Time O(n), Space O(n).

Sliding window is optimal.

Key Takeaways

Sliding Window: Fixed-size speed—smart!
Prefix Sum: Summed clarity—clear!
Averages: Sliding is fun.
Python Tip: Loops rock—see Python Basics.

Final Thoughts: Average That Subarray

LeetCode 643: Maximum Average Subarray I in Python is a neat array challenge. Sliding window offers speed and simplicity, while prefix sum provides a structured alternative. Want more? Try LeetCode 53: Maximum Subarray or LeetCode 209: Minimum Size Subarray Sum. Ready to slide? Head to Solve LeetCode 643 on LeetCode and find that max average today!