Find maximum average subarray of k length

Difficulty Level Easy
Frequently asked in Amazon
ArrayViews 1784

Problem Statement

You are given an array of integers and a number k. The problem statement asks to find maximum average subarray of k length. Subarray is nothing but an array composed from a contiguous block of the original array’s elements

Example

arr[] = {1,3,12,34,76,10}
[2, 4]

Explanation: Array starting from index 2 to index 4 holds the maximum average. Thus [2,4] is maximum average subarray of length 2.

arr[] = {1,-2,8,3,-6,9}
[1, 3]

Explanation: Array starting from index 1 to index 3 holds the maximum average.

 

Algorithm to find maximum average subarray of k length

1. Declare a currentSum.
2. Set the currentSum to arr[0].
3. Traverse the array from i=1 to less than the length of n.
  Store and update the addition of currentSum and arr[i] into the currentSum.
4. Set maximumSum to currentSum.
5. Set END to k-1.
6. Traverse the array from i=k to k to i < n.
7. Set sum to sum + arr[i] - arr[i - k].
  Check if the sum is greater than maximumSum.
    1. Set sum to maximumSum.
    2. Set END to i.
8. Return END – k + 1.

 

Explanation

We are given an array of integers and a number k. We have to find out the maximum average of sub-array of size k. This means the average we find should be of k contiguous numbers of the array. So we are going to find the average of k numbers within the sub-array. We have declared the condition if k is greater than n,. Return -1 if it is true. It means that if the value of k is greater than the value of n, which means we have not a valid value of k, it is not possible that k is greater than the size of the array.

We have already created the currentSum. Copy the first value of the given array to the currentSum. Then we will be traversing the array from index 1 because we already performed an operation on the value of currentSum. So we will be traversing the array and get the sum of previous element of currentSum and arr[i] and store it into the currentSum.

We have set the value of maximumSum to (k-1)th position of currentSum and END to k-1. Traverse the array from kth position till the last element of the array. We are going to get the difference arr[i] and arr[i – k] and we add it to the value of sum and store it to sum, and also we need not worry about the negative value we have started from the position k, so we won’t get any differences in there. If the sum is greater than the maximumSum, set the maximumSum from sum value and end value to i. We are going to repeat the same process until the length of an array is reached. Then we will return END – k + 1.

This technique is also referred to as Sliding Window Technique.

Find maximum average subarray of k length

 

Code to find maximum average subarray of k length

C++ Code

#include<iostream>
using namespace std;
int getMaxAvgSubArray(int arr[], int n, int k)
{
    if (k > n)
        return -1;
    int currentSum;
    currentSum = arr[0];
    for (int i = 1; i < n; i++)
        currentSum = currentSum + arr[i];
    int maximumSum = currentSum;
    int END = k - 1;
    for (int i = k; i < n; i++)
    {
        currentSum = currentSum + arr[i] - arr[i-k];
        if (currentSum > maximumSum)
        {
            maximumSum = currentSum;
            END = i;
        }
    }
    return END - k + 1;
}
int main()
{
    int arr[] = {1,3,12,34,76,10};
    int k = 3;
    int n = sizeof(arr)/sizeof(arr[0]);
    int start=getMaxAvgSubArray(arr, n, k);
    cout<<"Maximum average subarray: ["<< start<<" "<< (start + k - 1)<<"]";
    return 0;
}
Maximum average subarray: [2 4]

Java Code

class MaximumAverageSubarray
{
    public static int getMaxAvgSubArray(int []arr,int n, int k)
    {
        if (k > n)
            return -1;

        int currentSum = arr[0];

        for (int i = 1; i < k; i++)
            currentSum = currentSum + arr[i];

        int maximumSum = currentSum;
        int END = k - 1;

        for (int i = k; i < n; i++)
        {
            currentSum = currentSum + arr[i] - arr[i-k];

            if (currentSum > maximumSum)
            {
                maximumSum = currentSum;
                END = i;
            }
        }
        return END - k + 1;
    }
    public static void main (String[] args)
    {
        int []arr = {1,3,12,34,76,10};
        int k = 3;
        int n = arr.length;
        int start=getMaxAvgSubArray(arr, n, k);
        System.out.println("Maximum average subarray: ["+start+" "+ (start + k - 1)+"]");
    }
}

Maximum average subarray: [2 4]

Complexity Analysis

Time Complexity to find maximum average subarray of k length

Since we have traversed through the array once, we have linear time complexity. O(n) where “n” is the number of elements in the array.

Space Complexity to find maximum average subarray of k length

Since we used an array for storing the input, we have linear space complexity. O(n) where “n” is the number of elements in the array.

Translate »