643. Maximum Average Subarray I


Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Example 1:

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

Note:

  1. 1 <= k <= n <= 30,000.
  2. Elements of the given array will be in the range [-10,000, 10,000].


Solution

Approach #1 Cumulative Sum [Accepted]

Algorithm

We know that in order to obtain the averages of subarrays with length , we need to obtain the sum of these length subarrays. One of the methods of obtaining this sum is to make use of a cumulative sum array, , which is populated only once. Here, is used to store the sum of the elements of the given array from the first element upto the element at the index.

Once the array has been filled up, in order to find the sum of elements from the index to , all we need to do is to use: . Thus, now, by doing one more iteration over the array, we can determine the maximum average possible from the subarrays of length .

The following animation illustrates the process for a simple example.

!?!../Documents/643_Maximum_Average.json:1000,563!?!

Complexity Analysis

  • Time complexity : . We iterate over the array of length once to fill the array. Then, we iterate over elements of to determine the required result.

  • Space complexity : . We make use of a array of length to store the cumulative sum.

Approach #2 Sliding Window [Accepted]

Algorithm

Instead of creating a cumulative sum array first, and then traversing over it to determine the required sum, we can simply traverse over just once, and on the go keep on determining the sums possible for the subarrays of length . To understand the idea, assume that we already know the sum of elements from index to index , say it is .

Now, to determine the sum of elements from the index to the index , all we need to do is to subtract the element from and to add the element to . We can carry out our process based on this idea and determine the maximum possible average.

Complexity Analysis

  • Time complexity : . We iterate over the given array of length once only.

  • Space complexity : . Constant extra space is used.

Analysis written by: @vinod23

Submit Solution