Maximum Average Subarray II - Practice Coding Problems

Maximum Average Subarray II - Problem

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

Find a contiguous subarray whose length is greater than or 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.

Input & Output

Example 1 — Basic Case

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

› Output: 12.75000

💡 Note: Maximum average subarray is [12,-5,-6,50] with sum 51 and length 4, giving average 51/4 = 12.75

Example 2 — Minimum Length

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

› Output: 5.00000

💡 Note: Only one element, so the subarray [5] has average 5.0

Example 3 — All Negative

$ Input: nums = [-1,-2,-3,-4], k = 2

› Output: -1.50000

💡 Note: Best subarray is [-1,-2] with average (-1-2)/2 = -1.5

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,12,-5,-6,50,3] and k=4

Process

Find all subarrays length ≥ 4 and calculate averages

Output

Return maximum average found: 12.75

Key Takeaway

🎯 Key Insight: Binary search on the answer space is more efficient than checking all subarrays directly

Asked in

G Google 35 f Facebook 28 A Amazon 22

The key insight is to use binary search on the answer space rather than searching for subarrays directly. The optimal approach uses binary search on possible average values combined with a sliding window feasibility check. Time: O(n log(max-min)), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(1)	Check all possible subarrays of length ≥ k and find maximum average
Binary Search on Answer	O(n log(max-min))	O(n)	Binary search on the maximum possible average value
Prefix Sum Optimization	O(n²)	O(n)	Use prefix sums to calculate subarray sums in O(1) time

Brute Force — Algorithm Steps

Iterate through all possible starting positions
For each start, try all valid ending positions (length ≥ k)
Calculate average for each subarray and track maximum

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subarrays

Try all starting positions and valid lengths

Calculate Averages

Sum each subarray and divide by length

Track Maximum

Keep the highest average found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <float.h>

double solution(int* nums, int numsSize, int k) {
    double maxAvg = -DBL_MAX;
    
    for (int i = 0; i <= numsSize - k; i++) {
        for (int j = i + k - 1; j < numsSize; j++) {
            long long sum = 0;
            for (int l = i; l <= j; l++) {
                sum += nums[l];
            }
            double avg = (double) sum / (j - i + 1);
            if (avg > maxAvg) {
                maxAvg = avg;
            }
        }
    }
    
    return maxAvg;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[10000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    double result = solution(nums, numsSize, k);
    printf("%f\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Two nested loops for start/end positions O(n²), plus O(n) to calculate sum for each subarray

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables to track current sum and maximum average

✓ Linear Space

78.0K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler