Maximum Average Subarray I

🎯

Maximum Average Subarray I

easySLIDING_WINDOWAmazonGoogle

Imagine you are analyzing daily temperatures over a month and want to find the period of k consecutive days with the highest average temperature to plan a vacation.

💡 This problem is about finding the maximum average of any contiguous subarray of fixed length k. Beginners often struggle because they try to compute averages repeatedly from scratch, leading to inefficient solutions. Understanding how to efficiently slide over the array while updating sums is key.

📋

Problem Statement

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

1 ≤ nums.length ≤ 10^5-10^4 ≤ nums[i] ≤ 10^41 ≤ k ≤ nums.length

💡

Example

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

Output12.75

The subarray [12, -5, -6, 50] has the maximum average (51/4 = 12.75).

• k equals array length → average is entire array's average
• all negative numbers → maximum average is the least negative sum
• k = 1 → maximum average is the maximum element
• array with zeros → zeros affect average calculation

⚠️

Common Mistakes

Recomputing sum for every window from scratch

Leads to time limit exceeded on large inputs

✅ Use sliding window or prefix sums to update sums efficiently

Off-by-one errors in window boundaries

Incorrect sums or index out of range errors

✅ Carefully define loop ranges and window start/end indices

Returning integer division instead of float

Incorrect truncated average results

✅ Cast numerator or denominator to float/double before division

Not handling negative numbers correctly

Incorrect maximum average if negative sums are ignored

✅ Initialize max_sum to -infinity or minimum integer value

🧠

Brute Force (Nested Loops)

💡 This approach exists to build intuition by directly computing averages for every possible subarray of size k, which is straightforward but inefficient. It helps beginners understand the problem before optimizing.

Intuition

Check every contiguous subarray of length k, calculate its sum and average, and track the maximum average found.

Algorithm

1. Initialize max_sum as the sum of the first k elements.
2. For each subarray starting from index 1 to n-k, calculate the sum of k elements.
3. Update max_sum if the current sum is greater.
4. Return max_sum divided by k as the maximum average.

💡 The main challenge is realizing that recalculating sums repeatedly is inefficient but helps understand the problem.

</>

Code

def findMaxAverage(nums, k):
    n = len(nums)
    max_sum = float('-inf')
    for i in range(n - k + 1):
        current_sum = 0
        for j in range(i, i + k):
            current_sum += nums[j]
        if current_sum > max_sum:
            max_sum = current_sum
    return max_sum / k

# Driver code
if __name__ == '__main__':
    nums = [1,12,-5,-6,50,3]
    k = 4
    print(findMaxAverage(nums, k))  # Expected output: 12.75

Line Notes

def findMaxAverage(nums, k):Defines the function with input array and window size to encapsulate the logic.

for i in range(n - k + 1):Iterates over all possible starting indices for subarrays of length k to cover every window.

for j in range(i, i + k):Calculates sum of current subarray by iterating over k elements to get exact sum.

if current_sum > max_sum:Updates max_sum if current subarray sum is greater to track maximum found so far.

public class Solution {
    public static double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i <= n - k; i++) {
            int currentSum = 0;
            for (int j = i; j < i + k; j++) {
                currentSum += nums[j];
            }
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
        }
        return (double) maxSum / k;
    }

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

Line Notes

public static double findMaxAverage(int[] nums, int k)Method signature with input array and window size to define the solution method.

for (int i = 0; i <= n - k; i++)Loop over all valid starting indices for subarrays to cover every possible window.

for (int j = i; j < i + k; j++)Sum elements in the current subarray to compute exact sum for comparison.

if (currentSum > maxSum)Update maxSum if current sum is larger to keep track of maximum sum found.

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

double findMaxAverage(vector<int>& nums, int k) {
    int n = nums.size();
    int maxSum = INT_MIN;
    for (int i = 0; i <= n - k; i++) {
        int currentSum = 0;
        for (int j = i; j < i + k; j++) {
            currentSum += nums[j];
        }
        if (currentSum > maxSum) {
            maxSum = currentSum;
        }
    }
    return (double)maxSum / k;
}

int main() {
    vector<int> nums = {1,12,-5,-6,50,3};
    int k = 4;
    cout << findMaxAverage(nums, k) << endl; // Expected output: 12.75
    return 0;
}

Line Notes

double findMaxAverage(vector<int>& nums, int k)Function signature with vector reference and window size to define the solution.

for (int i = 0; i <= n - k; i++)Iterate over all possible subarray start indices to cover every window.

for (int j = i; j < i + k; j++)Sum elements in the current subarray to get exact sum for comparison.

if (currentSum > maxSum)Update maxSum if current sum is greater to track maximum sum found.

function findMaxAverage(nums, k) {
    const n = nums.length;
    let maxSum = -Infinity;
    for (let i = 0; i <= n - k; i++) {
        let currentSum = 0;
        for (let j = i; j < i + k; j++) {
            currentSum += nums[j];
        }
        if (currentSum > maxSum) {
            maxSum = currentSum;
        }
    }
    return maxSum / k;
}

// Test
const nums = [1,12,-5,-6,50,3];
const k = 4;
console.log(findMaxAverage(nums, k)); // Expected output: 12.75

Line Notes

function findMaxAverage(nums, k)Defines function with input array and window size to encapsulate logic.

for (let i = 0; i <= n - k; i++)Loops over all valid subarray start indices to cover every window.

for (let j = i; j < i + k; j++)Calculates sum of current subarray elements to get exact sum.

if (currentSum > maxSum)Updates maxSum if current sum is larger to track maximum sum found.

⏱

Complexity

TimeO(n*k)

SpaceO(1)

For each of the n-k+1 subarrays, we sum k elements, resulting in O(n*k) time. Space is constant as we only track sums and max.

💡 If n=100,000 and k=10,000, this means 1 billion operations, which is too slow for interviews.

Interview Verdict: TLE / Inefficient for large inputs

This approach is too slow for large inputs but is useful to understand the problem and correctness before optimizing.

🧠

Sliding Window (Optimal)

💡 This approach improves efficiency by reusing the sum from the previous window instead of recalculating it from scratch, which is a key insight in sliding window problems.

Intuition

Maintain a running sum of the current window of size k. When moving the window forward by one element, subtract the element leaving the window and add the new element entering.

Algorithm

1. Calculate the sum of the first k elements and store it as current_sum and max_sum.
2. Iterate from index k to the end of the array:
3. Subtract the element leaving the window (i-k) and add the new element (i) to current_sum.
4. Update max_sum if current_sum is greater.
5. Return max_sum divided by k as the maximum average.

💡 The key is to update the sum efficiently without recomputing the entire window sum each time.

</>

Code

def findMaxAverage(nums, k):
    n = len(nums)
    current_sum = sum(nums[:k])
    max_sum = current_sum
    for i in range(k, n):
        current_sum += nums[i] - nums[i - k]
        if current_sum > max_sum:
            max_sum = current_sum
    return max_sum / k

# Driver code
if __name__ == '__main__':
    nums = [1,12,-5,-6,50,3]
    k = 4
    print(findMaxAverage(nums, k))  # Expected output: 12.75

Line Notes

current_sum = sum(nums[:k])Initialize sum of first window to start sliding window calculation.

for i in range(k, n):Slide window from index k to end to cover all windows.

current_sum += nums[i] - nums[i - k]Update sum by removing left element and adding new right element efficiently.

if current_sum > max_sum:Track maximum sum found to return correct maximum average.

public class Solution {
    public static double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        int currentSum = 0;
        for (int i = 0; i < k; i++) {
            currentSum += nums[i];
        }
        int maxSum = currentSum;
        for (int i = k; i < n; i++) {
            currentSum += nums[i] - nums[i - k];
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
        }
        return (double) maxSum / k;
    }

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

Line Notes

for (int i = 0; i < k; i++)Calculate initial window sum to start sliding window.

for (int i = k; i < n; i++)Slide window through array to cover all windows.

currentSum += nums[i] - nums[i - k];Update sum by removing left and adding right element efficiently.

if (currentSum > maxSum)Update maxSum if current sum is greater to track maximum.

#include <iostream>
#include <vector>
using namespace std;

double findMaxAverage(vector<int>& nums, int k) {
    int n = nums.size();
    int currentSum = 0;
    for (int i = 0; i < k; i++) {
        currentSum += nums[i];
    }
    int maxSum = currentSum;
    for (int i = k; i < n; i++) {
        currentSum += nums[i] - nums[i - k];
        if (currentSum > maxSum) {
            maxSum = currentSum;
        }
    }
    return (double)maxSum / k;
}

int main() {
    vector<int> nums = {1,12,-5,-6,50,3};
    int k = 4;
    cout << findMaxAverage(nums, k) << endl; // Expected output: 12.75
    return 0;
}

Line Notes

for (int i = 0; i < k; i++)Sum first k elements to initialize window sum.

for (int i = k; i < n; i++)Slide window across array to cover all windows.

currentSum += nums[i] - nums[i - k];Update sum by removing left and adding right element efficiently.

if (currentSum > maxSum)Keep track of maximum sum found so far.

function findMaxAverage(nums, k) {
    const n = nums.length;
    let currentSum = 0;
    for (let i = 0; i < k; i++) {
        currentSum += nums[i];
    }
    let maxSum = currentSum;
    for (let i = k; i < n; i++) {
        currentSum += nums[i] - nums[i - k];
        if (currentSum > maxSum) {
            maxSum = currentSum;
        }
    }
    return maxSum / k;
}

// Test
const nums = [1,12,-5,-6,50,3];
const k = 4;
console.log(findMaxAverage(nums, k)); // Expected output: 12.75

Line Notes

for (let i = 0; i < k; i++)Initialize sum of first window to start sliding window.

for (let i = k; i < n; i++)Slide window through array to cover all windows.

currentSum += nums[i] - nums[i - k];Update sum by removing left and adding right element efficiently.

if (currentSum > maxSum)Update maxSum if current sum is greater to track maximum.

⏱

Complexity

TimeO(n)

SpaceO(1)

We compute the initial sum in O(k), then slide the window across the array in O(n-k) steps, each updating sum in O(1). Total O(n). Space is constant.

💡 For n=100,000 and k=10,000, this means about 110,000 operations, which is efficient for interviews.

Interview Verdict: Accepted / Optimal

This is the preferred approach in interviews due to its efficiency and clarity.

🧠

Prefix Sum Array (Alternative Optimal)

💡 This approach uses prefix sums to compute subarray sums in O(1) after O(n) preprocessing, offering an alternative to sliding window with similar efficiency.

Intuition

Precompute prefix sums so that sum of any subarray can be found by subtracting two prefix sums. Then iterate over all subarrays of length k to find the maximum sum.

Algorithm

1. Create a prefix sum array where prefix[i] is sum of nums[0..i-1].
2. Iterate over all subarrays of length k using prefix sums to get their sums in O(1).
3. Track the maximum sum found.
4. Return the maximum sum divided by k.

💡 The key is to understand how prefix sums allow constant-time subarray sum queries.

</>

Code

def findMaxAverage(nums, k):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    max_sum = float('-inf')
    for i in range(k, n + 1):
        current_sum = prefix[i] - prefix[i - k]
        if current_sum > max_sum:
            max_sum = current_sum
    return max_sum / k

# Driver code
if __name__ == '__main__':
    nums = [1,12,-5,-6,50,3]
    k = 4
    print(findMaxAverage(nums, k))  # Expected output: 12.75

Line Notes

prefix = [0] * (n + 1)Initialize prefix sum array with extra space to handle sums easily.

prefix[i + 1] = prefix[i] + nums[i]Build prefix sums cumulatively to enable O(1) subarray sum queries.

current_sum = prefix[i] - prefix[i - k]Calculate sum of subarray using prefix sums efficiently.

if current_sum > max_sum:Update max_sum if current sum is greater to track maximum.

public class Solution {
    public static double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        prefix[0] = 0;
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        int maxSum = Integer.MIN_VALUE;
        for (int i = k; i <= n; i++) {
            int currentSum = prefix[i] - prefix[i - k];
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
        }
        return (double) maxSum / k;
    }

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

Line Notes

int[] prefix = new int[n + 1];Create prefix sum array with extra space for easy indexing.

prefix[i + 1] = prefix[i] + nums[i];Build prefix sums cumulatively for O(1) subarray sum queries.

int currentSum = prefix[i] - prefix[i - k];Calculate subarray sum in O(1) using prefix sums.

if (currentSum > maxSum)Update maxSum if current sum is greater to track maximum.

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

double findMaxAverage(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    int maxSum = INT_MIN;
    for (int i = k; i <= n; i++) {
        int currentSum = prefix[i] - prefix[i - k];
        if (currentSum > maxSum) {
            maxSum = currentSum;
        }
    }
    return (double)maxSum / k;
}

int main() {
    vector<int> nums = {1,12,-5,-6,50,3};
    int k = 4;
    cout << findMaxAverage(nums, k) << endl; // Expected output: 12.75
    return 0;
}

Line Notes

vector<int> prefix(n + 1, 0);Initialize prefix sum vector with zeros for easy indexing.

prefix[i + 1] = prefix[i] + nums[i];Build prefix sums cumulatively for efficient queries.

int currentSum = prefix[i] - prefix[i - k];Calculate subarray sum in O(1) using prefix sums.

if (currentSum > maxSum)Update maxSum if current sum is greater to track maximum.

function findMaxAverage(nums, k) {
    const n = nums.length;
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    let maxSum = -Infinity;
    for (let i = k; i <= n; i++) {
        let currentSum = prefix[i] - prefix[i - k];
        if (currentSum > maxSum) {
            maxSum = currentSum;
        }
    }
    return maxSum / k;
}

// Test
const nums = [1,12,-5,-6,50,3];
const k = 4;
console.log(findMaxAverage(nums, k)); // Expected output: 12.75

Line Notes

const prefix = new Array(n + 1).fill(0);Initialize prefix sum array with zeros for easy indexing.

prefix[i + 1] = prefix[i] + nums[i];Build prefix sums cumulatively for efficient subarray sum queries.

let currentSum = prefix[i] - prefix[i - k];Calculate subarray sum in O(1) using prefix sums.

if (currentSum > maxSum)Update maxSum if current sum is greater to track maximum.

⏱

Complexity

TimeO(n)

SpaceO(n)

Prefix sums are computed in O(n), then each subarray sum is computed in O(1) for O(n) total. Space is O(n) for prefix array.

💡 For n=100,000, this means 100,000 operations plus storing 100,000 prefix sums, which is efficient but uses extra memory.

Interview Verdict: Accepted / Optimal alternative

This approach is also optimal and useful when multiple subarray sum queries are needed.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, code the sliding window approach because it is optimal, easy to implement, and uses constant space.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n*k)	O(1)	No	N/A	Mention only - never code due to inefficiency
2. Sliding Window	O(n)	O(1)	No	Yes (track indices)	Code this approach for optimal solution
3. Prefix Sum	O(n)	O(n)	No	Yes	Good alternative, especially if multiple queries

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding.Step 3: Explain the inefficiency and introduce the sliding window optimization.Step 4: Code the sliding window solution carefully.Step 5: Discuss alternative prefix sum approach if time permits.Step 6: Test your code with edge cases and explain complexity.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

The interviewer tests your ability to identify the sliding window pattern, optimize from brute force, write clean code, and handle edge cases.

Common Follow-ups

• What if k is very large or equals array length? → Handle gracefully, no change needed.
• Can you find the subarray itself, not just the average? → Track start index during sliding window.

💡 These follow-ups test your ability to adapt the solution and extract more information from the problem.

🔍

Pattern Recognition

When to Use

1) Problem asks for max/min average or sum of fixed-length subarray; 2) Input is an array; 3) Need contiguous elements; 4) Constraints require O(n) or better solution.

Signature Phrases

maximum average subarray of size kcontiguous subarrayfixed window size

NOT This Pattern When

Variable size window problems or problems requiring non-contiguous subsequences are different patterns.

Similar Problems

Maximum Sum Subarray of Size K - similar sum instead of averageSliding Window Maximum - sliding window with max instead of average

Practice

1. Consider the following Python code snippet implementing the optimal sliding window approach to count subarrays with at most k odd numbers. What is the final return value when calling countNiceSubarrays([1,2,1], 2)?

def countAtMost(nums, k):
    count = 0
    left = 0
    odd_count = 0
    for right in range(len(nums)):
        if nums[right] % 2 == 1:
            odd_count += 1
        while odd_count > k:
            if nums[left] % 2 == 1:
                odd_count -= 1
            left += 1
        count += right - left + 1
    return count

def countNiceSubarrays(nums, k):
    return countAtMost(nums, k) - countAtMost(nums, k - 1)

easy

A. 3

B. 1

C. 2

D. 4

Solution

1. Step 1: Calculate countAtMost(nums, 2)

   Iterate right pointer: - right=0 (1 odd): count=1 - right=1 (1 odd): count=1+(1-0+1)=3 - right=2 (2 odds): count=3+(2-0+1)=6 So countAtMost(nums,2)=6

2. Step 2: Calculate countAtMost(nums, 1)

   Iterate right pointer: - right=0 (1 odd): count=1 - right=1 (1 odd): count=1+(1-0+1)=3 - right=2 (2 odds >1): move left to 1, odd_count=1, count=3+(2-1+1)=5 So countAtMost(nums,1)=5 Finally, countNiceSubarrays=6-5=1

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Manual trace confirms result 1 [OK]

Hint: Subtract countAtMost(k-1) from countAtMost(k) [OK]

Common Mistakes:

• Off-by-one in counting subarrays
• Miscounting odd numbers during window shrink
• Confusing countAtMost with exact count

2. What is the time complexity of the optimal sliding window solution for the fruits problem, given an input array of length n? Assume fruit types are arbitrary integers but the number of distinct fruit types in the window is limited to two.

medium

A. O(n) because each element is visited at most twice by the two pointers

B. O(n log n) due to maintaining the hash map keys in sorted order

C. O(n²) because the inner while loop can run multiple times per outer iteration

D. O(n * k) where k is the number of distinct fruit types in the array

Solution

1. Step 1: Analyze outer and inner loops

   The right pointer moves from 0 to n-1 once; the left pointer only moves forward when shrinking window.

2. Step 2: Each element is added and removed at most once

   Thus total operations are proportional to 2n, which is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer sliding window with hashmap is linear time [OK]

Hint: Two pointers each move forward at most n times [OK]

Common Mistakes:

• Assuming nested loops multiply to n²
• Thinking hashmap operations add log n
• Confusing distinct fruit count with input size

3. The following code attempts to solve the Max Consecutive Ones III problem. Identify the line that contains a subtle bug causing incorrect results on some inputs.

from collections import deque

def longestOnes(nums, k):
    zero_positions = deque()
    left = 0
    max_length = 0
    for right in range(len(nums)):
        if nums[right] == 0:
            zero_positions.append(right)
        max_length = max(max_length, right - left + 1)
        if len(zero_positions) > k:
            left = zero_positions.popleft() + 1
    return max_length

medium

A. Line returning max_length at the end

B. Line appending zero index to zero_positions

C. Line updating max_length before shrinking the window

D. Line initializing left pointer to 0

Solution

1. Step 1: Understand window shrinking condition

   The window must shrink before updating max_length to ensure the window contains at most k zeros.

2. Step 2: Identify bug in max_length update timing

   Updating max_length before shrinking allows counting invalid windows with more than k zeros, causing incorrect max_length.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Moving max_length update after shrinking fixes correctness [OK]

Hint: Update max_length only after window is valid [OK]

Common Mistakes:

• Updating max_length before shrinking window
• Not shrinking window at all
• Incorrect zero count tracking

4. What is the time complexity of the optimal sliding window solution for the Maximum Points You Can Obtain from Cards problem, and why?

medium

A. O(n) because it computes the total sum once and slides a window of size n-k across the array once.

B. O(k^2) because it tries all combinations of picking cards from ends.

C. O(n*k) because it sums subarrays of size n-k repeatedly inside a loop of size k.

D. O(n log n) because it sorts the array before applying the sliding window.

Solution

1. Step 1: Analyze the operations

   The algorithm sums all elements once (O(n)) and then slides a window of size n-k across the array once, updating sums in O(1) per step.

2. Step 2: Confirm no nested loops or sorting

   There is no nested iteration or sorting, so total time is linear in n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass sliding window and sum -> O(n) time [OK]

Hint: Sliding window updates in O(1) per step yield O(n) total [OK]

Common Mistakes:

• Confusing repeated sum computations as O(n*k)
• Assuming sorting is needed
• Thinking brute force complexity applies

5. Suppose the sliding window maximum problem is modified so that elements can be reused multiple times (i.e., the window can slide but elements may appear multiple times in the output). Which of the following statements about the monotonic deque approach is true?

hard

A. The monotonic deque approach fails because it assumes each element appears only once; a max-heap is required instead.

B. The monotonic deque approach must be modified to track counts of elements to handle reuse correctly.

C. The monotonic deque approach works without any changes since it only depends on indices.

D. The problem reduces to a different pattern; monotonic deque is not applicable and a segment tree is needed.

Solution

1. Step 1: Understand the reuse modification

   Allowing elements to be reused means the same element can contribute multiple times as the window slides, potentially overlapping.

2. Step 2: Analyze monotonic deque assumptions

   The original deque stores indices assuming each element appears once per position. To handle reuse, counts or frequency tracking is needed to maintain correctness.

3. Step 3: Evaluate other options

   Monotonic deque without modification fails; max-heap alone is inefficient; segment tree is overkill for this variant.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Tracking counts allows correct max maintenance with reuse [OK]

Hint: Reuse breaks unique index assumption; track counts to fix [OK]

Common Mistakes:

• Assuming no changes needed for reuse
• Switching to max-heap without efficiency gain
• Thinking monotonic deque is inapplicable