Skip to main content
Talentd

Maximum Average Subarray I - Solution & Explanation

EasyArraySliding Window15 min readAsked at: Amazon, Microsoft, Goldman Sachs +9
Practice this problem

Problem Statement

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.

 

Example 1:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Example 2:

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

 

Constraints:

  • n == nums.length
  • 1 <= k <= n <= 105
  • -104 <= nums[i] <= 104

Approach Overview

Problem Overview: You are given an integer array nums and an integer k. The task is to find the contiguous subarray of length k that has the maximum average value and return that average. Since the subarray size is fixed, the main challenge is computing sums efficiently without recomputing the same elements repeatedly.

Approach 1: Brute Force (Time: O(n*k), Space: O(1))

The most direct method checks every subarray of size k. Start from index 0, sum the next k elements, compute the average, and track the maximum value. Move the starting index one step to the right and repeat until all possible windows are processed. Each window requires summing k elements, which leads to O(n*k) time complexity for an array of length n. Space usage stays O(1) since only a few variables store the running sum and maximum average.

This approach is easy to implement and helps you understand the problem mechanics. However, it repeatedly recalculates overlapping sums. For large arrays or large k, the redundant computation becomes expensive. The inefficiency comes from recomputing nearly the same window sum every iteration.

Approach 2: Sliding Window Technique (Time: O(n), Space: O(1))

The optimal solution uses a sliding window over the array. Instead of recalculating the entire sum for every window, compute the sum of the first k elements once. This represents the first window. Then slide the window forward by one position: subtract the element leaving the window and add the new element entering the window.

This update takes constant time. As you move the window from left to right, maintain the maximum window sum encountered. After processing the entire array, divide the maximum sum by k to obtain the maximum average. Because each element enters and leaves the window at most once, the algorithm runs in O(n) time with O(1) extra space.

The key insight is that consecutive windows share k-1 elements. Updating the sum incrementally avoids redundant work. This pattern appears frequently in problems involving fixed-size subarrays, streaming data, or running aggregates. Sliding window is often paired with array traversal problems and is a fundamental technique for interview preparation.

Recommended for interviews: Interviewers expect the Sliding Window approach. The brute force solution shows you understand the problem definition, but it does not scale well. The sliding window demonstrates that you recognize overlapping computations and can optimize them to achieve O(n) time complexity with constant space.

Approach 1: Using Sliding Window Technique

The sliding window technique allows us to keep track of the sum of a subarray of fixed length k by adding one new element and removing the first element of the previous window, thus achieving O(n) time complexity.

The C code initializes a sum of the first k elements and iterates over the elements from k to the end of the array. It updates the sum to add the current element and subtract the element that is sliding out of the window, then updates maxSum if the new sum is greater. Finally, it returns the maximum average.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Brute Force Approach

The brute force approach involves checking every possible subarray of length k and calculating its average, then keeping track of the maximum average found. However, this approach is not efficient for large inputs.

The C solution calculates the sum and average of every subarray of length k, updating the maximum average found. This implementation is simple but inefficient for large arrays due to its O(n*k) complexity.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n*k)
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Sliding Window

We maintain a sliding window of length k, and for each window, we calculate the sum s of the numbers within the window. We take the maximum sum s as the answer.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustPHP

Python

Java

C++

Go

TypeScript

Rust

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Sliding Window Technique

Time Complexity: O(n)
Space Complexity: O(1)

Brute Force Approach

Time Complexity: O(n*k)
Space Complexity: O(1)

Sliding Window—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute ForceO(n*k)O(1)Good for understanding the problem or when k is extremely small
Sliding WindowO(n)O(1)Best choice for fixed-size subarray problems and interview solutions

Video Solution

Maximum Average Subarray (LeetCode 643) | Sliding Window Algorithm | Full solution with animations • Nikhil Lohia • 50,691 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Average Subarray I easy or hard?
Maximum Average Subarray I is classified as an Easy problem on LeetCode. The challenge mainly tests understanding of the sliding window pattern and recognizing that overlapping subarray sums can be updated incrementally instead of recomputed.
How to solve Maximum Average Subarray I in O(n)?
Use a sliding window of size k. First compute the sum of the first k elements. Then iterate from index k to the end of the array, updating the window sum by subtracting nums[i-k] and adding nums[i]. Track the maximum sum during traversal and divide by k to get the maximum average.
Maximum Average Subarray I Python or Java solution?
Both Python and Java implementations follow the same sliding window logic. Compute the first window sum of k elements, then update the sum while moving the window forward. This ensures O(n) time complexity and constant extra space regardless of the language.
What is the best approach for Maximum Average Subarray I?
The sliding window approach is the best solution. Compute the sum of the first k elements, then slide the window across the array by subtracting the element leaving the window and adding the new element entering it. This reduces the time complexity to O(n) with O(1) extra space.
What data structure is used in Maximum Average Subarray I?
The problem primarily uses arrays along with the sliding window technique. No additional data structures are required because the algorithm maintains only a running sum and a maximum value while iterating through the array.
What is the time complexity of Maximum Average Subarray I?
The optimal sliding window solution runs in O(n) time because each element is processed once as the window moves across the array. The brute force method requires O(n*k) time since it recalculates the sum of k elements for every starting index.
Is Maximum Average Subarray I asked at Google, Amazon, or Meta?
Maximum Average Subarray I is a common entry-level array and sliding window problem frequently used in coding interviews and online assessments. Variations of fixed-size window problems appear in interviews at companies like Amazon, Google, and Meta to test array traversal and optimization skills.

Ready to solve this problem?

Practice Maximum Average Subarray I with our built-in code editor and test cases.

Practice on FleetCode
Previous

K Radius Subarray Averages

Next

Maximum Average Subarray II