Maximum Average Subarray I

📋

Problem

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.

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

Edge cases: k equals array length → average is entire array's averageall negative numbers → maximum average is the least negative sumk = 1 → maximum average is the maximum element

</>

IDE

def findMaxAverage(nums: list[int], k: int) -> float:public double findMaxAverage(int[] nums, int k)double findMaxAverage(vector<int>& nums, int k)function findMaxAverage(nums, k)

def findMaxAverage(nums, k):
    # Write your solution here
    pass

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        // Write your solution here
        return 0.0;
    }
}

#include <vector>
using namespace std;

double findMaxAverage(vector<int>& nums, int k) {
    // Write your solution here
    return 0.0;
}

function findMaxAverage(nums, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: max element value instead of max averageGreedy approach picking max element only, ignoring window size k.✅ Check all contiguous subarrays of length k using sliding window; do not pick single elements.

Wrong: integer division truncation causing wrong averageUsing integer division instead of floating point division.✅ Use floating point division (e.g., convert sum or k to float/double before division).

Wrong: incorrect max sum initialization causing failure on negative numbersInitializing max sum to 0 instead of -inf, failing when all sums are negative.✅ Initialize max sum to float('-inf') or minimum possible value.

Wrong: TLE on large inputsUsing nested loops O(n*k) instead of sliding window O(n).✅ Implement sliding window to update sum in O(1) per step.

✓

Test Cases

Try testing your solution on edge cases like k=1 or k equals array length to ensure robustness.

Consider tricky inputs that might fool greedy approaches or mishandle boundaries.

Prepare for performance tests by optimizing your solution to linear time complexity.

t1_01basic

Input{"nums":[1,12,-5,-6,50,3],"k":4}

Expected12.75

⏱ Performance - must finish in 2000ms

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

💡 Consider using a sliding window to track sums of subarrays of length k.

💡 Maintain a running sum and update it by subtracting the element leaving the window and adding the new element.

💡 Return the maximum sum divided by k to get the maximum average.

Why it failed: Incorrect output means the sliding window sum update is wrong; ensure you subtract the leftmost element and add the new rightmost element correctly.

✓ Correctly implemented sliding window with proper sum updates.

t1_02basic

Input{"nums":[5,5,5,5,5,5],"k":3}

Expected5

⏱ Performance - must finish in 2000ms

All subarrays of length 3 have sum 15, average 5.0.

💡 If all elements are equal, any subarray of length k has the same average.

💡 Check that your code handles uniform arrays without error.

💡 Verify that the maximum average equals the element value when all are identical.

Why it failed: Failing this test suggests incorrect handling of uniform arrays or averaging logic; ensure sum and division are correct.

✓ Correctly handles uniform arrays and computes average properly.

t2_01edge

Input{"nums":[10,-10,10,-10],"k":4}

Expected0

⏱ Performance - must finish in 2000ms

k equals array length; average is sum of entire array (0) divided by 4 = 0.0.

💡 When k equals the array length, the answer is the average of the entire array.

💡 Check that your code handles this boundary without errors.

💡 Sum all elements once and divide by k when k == nums.length.

Why it failed: Failing this test means boundary condition for k == nums.length is not handled; fix by allowing full array sum calculation.

✓ Correctly handles full array average when k equals array length.

t2_02edge

Input{"nums":[-5,-2,-3,-4],"k":2}

Expected-2.5

⏱ Performance - must finish in 2000ms

Maximum average subarray is [-2, -3] with sum -5 and average -2.5 (least negative).

💡 Negative numbers require careful sum tracking; maximum average is the least negative sum.

💡 Sliding window logic remains the same even with negative values.

💡 Ensure you update max sum correctly even if all sums are negative.

Why it failed: Failing this test indicates max sum initialization or update logic does not handle negative sums; initialize max sum to -inf and update properly.

✓ Correctly computes maximum average with negative numbers.

t2_03edge

Input{"nums":[0,0,0,0,0],"k":3}

Expected0

⏱ Performance - must finish in 2000ms

All zeros; any subarray of length 3 has average 0.0.

💡 Zeros affect sum and average but should not cause errors.

💡 Check that your code does not skip zero sums or treat them as special cases.

💡 Verify that max sum can be zero and is updated correctly.

Why it failed: Failing this test suggests incorrect handling of zero sums; ensure max sum can be zero and is updated accordingly.

✓ Correctly handles zero values and computes average.

t3_01corner

Input{"nums":[1,100,1,100,1],"k":2}

Expected50.5

⏱ Performance - must finish in 2000ms

Maximum average subarray is [100,1] or [1,100] with sum 101 and average 50.5. The previous expected value 100.5 was incorrect.

💡 Beware of greedy approaches that pick only the largest element ignoring window size.

💡 Sliding window must consider all contiguous subarrays of length k.

💡 Check all windows of size k and pick the maximum average, not just max element.

Why it failed: Failing this test means greedy approach picking max element only; fix by checking all windows of length k.

✓ Correctly evaluates all windows and finds maximum average.

t3_02corner

Input{"nums":[1,2,3,4,5],"k":1}

Expected5

⏱ Performance - must finish in 2000ms

k=1 means maximum average is maximum element, which is 5.

💡 When k=1, the problem reduces to finding the maximum element.

💡 Check that your code handles k=1 correctly without errors.

💡 Return the maximum element as the maximum average for k=1.

Why it failed: Failing this test means code does not handle k=1 correctly; fix by returning max element when k=1.

✓ Correctly handles k=1 by returning max element.

t3_03corner

Input{"nums":[1,2,3,4,5],"k":5}

Expected3

⏱ Performance - must finish in 2000ms

k equals array length; average is sum(1..5)/5 = 15/5 = 3.0.

💡 Check boundary condition where k equals array length.

💡 Ensure sum of entire array is computed correctly.

💡 Return total sum divided by k for this case.

Why it failed: Failing this test means boundary condition for k == nums.length not handled; fix by summing entire array.

✓ Correctly handles full array average when k equals array length.

t4_01performance

Input{"nums":[10000,-10000,9999,-9999,10000,-10000,9999,-9999,10000,-10000,9999,-9999,10000,-10000,9999,-9999,10000,-10000,9999,-9999,10000,-10000,9999,-9999,10000,-10000,9999,-9999,10000,-10000,9999,-9999,10000,-10000,9999,-9999,10000,-10000,9999,-9999,10000,-10000,9999,-9999,10000,-10000,9999,-9999,10000,-10000,9999,-9999,10000,-10000,9999,-9999,10000,-10000,9999,-9999,10000,-10000,9999,-9999,10000,-10000,9999,-9999,10000,-10000,9999,-9999,10000,-10000,9999,-9999,10000,-10000,9999,-9999,10000,-10000,9999,-9999,10000,-10000,9999,-9999,10000,-10000,9999,-9999],"k":50}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, k=50; O(n*k) brute force will time out; optimal O(n) sliding window required.

💡 Brute force O(n*k) is too slow for n=100 and k=50.

💡 Use sliding window technique to achieve O(n) time complexity.

💡 Maintain running sum and update by subtracting left element and adding right element.

Why it failed: TLE occurs due to nested loops O(n*k); fix by implementing sliding window with O(n) complexity.

✓ Solution runs within time limit using O(n) sliding window approach.

Practice

1. Given the following code and input cardPoints = [4, 2, 3, 1], k = 2, what is the value of min_subarray_sum after the loop finishes?

easy

A. 3

B. 5

C. 4

D. 6

Solution

1. Step 1: Calculate initial sums

   n=4, k=2, window_size=2, current_sum=sum([4,2])=6, min_subarray_sum=6

2. Step 2: Iterate over the array

   i=2: current_sum=6 + 3 - 4 = 5, min_subarray_sum=5
   i=3: current_sum=5 + 1 - 2 = 4, min_subarray_sum=4

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Minimum subarray sum found is 4 after sliding window moves [OK]

Hint: Sliding window updates sum by adding new and removing old element [OK]

Common Mistakes:

• Off-by-one error in loop range
• Incorrect initial window sum
• Not updating min_subarray_sum correctly

2. The following code attempts to find the maximum sum subarray of size k using the sliding window approach. Identify the line that contains a subtle bug that may cause incorrect results when the array contains all negative numbers.

def max_sum_subarray_sliding_window(arr, k):
    n = len(arr)
    window_sum = sum(arr[:k])
    max_sum = 0
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]
        if window_sum > max_sum:
            max_sum = window_sum
    return max_sum

medium

A. Line 4: Initializing max_sum to 0 instead of a smaller value.

B. Line 5: Loop starting from index k instead of k-1.

C. Line 3: Initializing window_sum with sum of first k elements.

D. Line 6: Updating window_sum by adding arr[i] and subtracting arr[i - k].

Solution

1. Step 1: Understand initialization of max_sum

   max_sum is initialized to 0, which is incorrect if all array elements are negative because the maximum sum could be less than 0.

2. Step 2: Consequence of wrong initialization

   If all sums are negative, max_sum remains 0, which is incorrect. Proper initialization should be max_sum = window_sum (sum of first k elements) or float('-inf').

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   max_sum initialized to 0 causes incorrect max for negative arrays [OK]

Hint: Initialize max_sum to first window sum, not zero [OK]

Common Mistakes:

• Initializing max_sum to zero instead of first window sum
• Off-by-one errors in loop indices
• Incorrect window_sum updates

3. The following code attempts to find the minimum length of a subarray containing duplicate cards. Identify the bug that causes incorrect results on some inputs.

def minimumCardPickup(cards):
    last_seen = {}
    left = 0
    min_len = float('inf')
    for right, card in enumerate(cards):
        if card in last_seen and last_seen[card] < left:
            left = last_seen[card] + 1
        last_seen[card] = right
        if right - left + 1 > 1:
            min_len = min(min_len, right - left + 1)
    return min_len if min_len != float('inf') else -1

medium

A. Line 9: The min_len update should only happen if right - left + 1 >= 2

B. Line 7: last_seen[card] should be updated before the if condition

C. Line 3: min_len should be initialized to 0 instead of infinity

D. Line 5: The condition should check if last_seen[card] >= left, not < left

Solution

1. Step 1: Analyze condition for moving left pointer

   The code moves left pointer only if last_seen[card] < left, which is incorrect. It should move left if last_seen[card] ≥ left to shrink window past duplicate.

2. Step 2: Effect of incorrect condition

   Because of this, left pointer may not move when duplicate is inside current window, causing incorrect min_len or missing duplicates.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct condition is last_seen[card] ≥ left to update left pointer [OK]

Hint: Check if duplicate index is inside current window (≥ left) [OK]

Common Mistakes:

• Using < instead of ≥ in duplicate check
• Updating last_seen before checking duplicates

4. What is the time complexity of the optimized sliding window algorithm that uses filtered characters for the minimum window substring problem, where n is the length of s and m is the length of t?

medium

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

B. O(n * m) because for each character in s we check all characters in t

C. O(n + m) because we filter s and then slide over filtered characters

D. O(n^2) because shrinking and expanding the window can cause nested loops

Solution

1. Step 1: Identify main loops

   The algorithm uses two pointers moving over filtered characters, each pointer advances at most n times.

2. Step 2: Analyze filtering and counting

   Filtering s takes O(n), sliding window over filtered characters is O(n) since each character is visited twice max.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer sliding window is linear time [OK]

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

Common Mistakes:

• Confusing filtering cost
• Assuming nested loops cause O(n^2)
• Ignoring that each pointer moves only forward

5. Suppose you want to find the longest substring with at most k distinct characters, but now characters can be reused infinitely many times and the string is extremely long. Which modification to the sliding window approach is necessary to handle this efficiently?

hard

A. Use a frequency map with counts and shrink window when counts exceed k distinct characters, ignoring last seen positions

B. Maintain an ordered dictionary of last seen indices and shrink window as usual; no change needed

C. Use a frequency map and shrink the window only when distinct characters exceed k, ignoring last seen indices

D. Switch to a brute force approach since reuse breaks sliding window assumptions

Solution

1. Step 1: Understand reuse impact

   When characters can be reused infinitely, tracking last seen indices is insufficient; frequency counts are needed.

2. Step 2: Modify approach

   Use a frequency map to count occurrences and shrink window when distinct characters exceed k, ignoring last seen positions.

3. Step 3: Confirm efficiency

   This approach maintains O(n) time and handles reuse correctly.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Frequency map with counts is required for reuse scenarios [OK]

Hint: Frequency counts needed when characters can be reused infinitely [OK]

Common Mistakes:

• Assuming last seen indices suffice for reuse
• Thinking brute force is necessary