Scale Engineer

Maximum Average Subarray I

Easy
#0597Time: O(n * k). The outer loop runs `n-k+1` times, and for each iteration, the inner loop runs `k` times to calculate the sum. This results in a total of approximately `n * k` operations.Space: O(1). We only use a few variables to store the sums and loop indices, regardless of the input size.
Patterns
Sliding Window
Data structures
Array

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach iterates through every possible contiguous subarray of length k, calculates the sum of each subarray, and finds the maximum sum. The maximum average is then this maximum sum divided by k.

Algorithm

  • Initialize a variable maxSum to a very small number (e.g., Long.MIN_VALUE).
  • Iterate with an index i from 0 to n-k, where n is the length of the array. This index i will be the starting point of our subarray.
  • For each i, create an inner loop with index j from i to i+k-1 to calculate the sum of the current subarray.
  • Store this sum in a variable currentSum.
  • After the inner loop, compare currentSum with maxSum and update maxSum = Math.max(maxSum, currentSum).
  • After the outer loop finishes, return maxSum / k.

Walkthrough

The simplest way to solve this problem is to consider every possible subarray of length k one by one.

We can use a nested loop structure. The outer loop iterates through all possible starting indices of the subarray, from 0 to n-k.

For each starting index i, the inner loop calculates the sum of the elements from nums[i] to nums[i+k-1].

We maintain a variable, say maxSum, to store the maximum sum found so far. After calculating the sum of a subarray, we compare it with maxSum and update maxSum if the current sum is greater.

After the loops complete, maxSum will hold the maximum sum of any contiguous subarray of length k. The final result is maxSum / k.

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

Complexity

Time

O(n * k). The outer loop runs `n-k+1` times, and for each iteration, the inner loop runs `k` times to calculate the sum. This results in a total of approximately `n * k` operations.

Space

O(1). We only use a few variables to store the sums and loop indices, regardless of the input size.

Trade-offs

Pros

  • Simple to understand and implement.

Cons

  • Inefficient for large inputs, likely to result in a 'Time Limit Exceeded' error on competitive programming platforms due to the O(n*k) complexity.

Solutions

class Solution {public  double findMaxAverage(int[] nums, int k) {    int s = 0;    for (int i = 0; i < k; ++i) {      s += nums[i];    }    int ans = s;    for (int i = k; i < nums.length; ++i) {      s += (nums[i] - nums[i - k]);      ans = Math.max(ans, s);    }    return ans * 1.0 / k;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem