Find the subarray with least average

Problem Statement

You have given an integer array and a number k. The problem statement asks to find the subarray with least average, which is to find out the sub-array of k elements, which has the minimum average.

Example

arr[] = {12, 34, 20, 30, 24, 45}
k = 3

Sub-Array of [0, 2] has a minimum average.

Explanation: 12, 34, and 20 will be a sub-array of size k which has the least average among all possible sub-arrays.

arr[] = {42, 20, 15, 26, 10, 33}
k = 3

Sub-Array of [2, 4] has a minimum average.

Explanation: 15, 26, and 10 will be a sub-array of size k which has the least average among all possible sub-arrays.

Algorithm to find the subarray with least average

1. Set start and sum to 0.
2. Traverse the array up to the k, and keep storing the sum of all array elements into the sum.
3. Set leastSum to sum.
4. Traverse the array starting from i=k till i<n.
    1. Get the addition of arr[i] - arr[i-k] and update the value of sum and update it into the sum.
    2. Check if the sum is less than leastSum, if true then update the leastSum to sum and set update start to i-k+1.
5. Print start and start+k-1.

Explanation

We have an array of integers and a number k. Our task is to find out the minimum average among all the possible sub-arrays of size k. We have the condition in there if n is less than k, it means if we pass the size of sub-arrays of which we need to find the minimum average. That array is greater than the size of the whole array, then it is not possible to find that sub-array average. After setting up the value of sum and start to 0. We will be traversing the array and for the first traversal till the value of k. We will be picking up each element of an array and adding up into the sum, then update it. Some value will be in sum after the complete traversal, and that is the sum of all the values present in a sub-array.

The next thing we are going to do is copying the value of sum to leastSum, because we will be finding the minimum average among all the sub-array of size k. We will first traverse the array from start until first k elements, and store the sum in the leastSum. Afterward we will be adding arr[i] – arr[i-k] to leastSum for each i. This is just we have two values now we are looking for third and checking for least. Then what we will check for is if leastSum is less than k, if true, then we will be updating the value of leastSum and also the value of start to i-k+1. This equation of updation is just because to keep the output as indexing of an array normal because we started with the k, so we will need to adjust it.

After the traversal, we have the value of start but we don’t have the ending value of sub-array which has minimum average, we will just put the start+k-1, this will help in finding out the ending index of the sub-array.

Code to find the subarray with least average

C++ code

#include<iostream>

using namespace std;

void getMinimumAvgSubarray(int arr[], int n, int k)
{
    if (n < k)
        return;

    int start = 0;

    int sum = 0;
    for (int i = 0; i < k; i++)
        sum += arr[i];

    int leastSum = sum;

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

        if (sum < leastSum)
        {
            leastSum = sum;
            start = (i - k + 1);
        }
    }
    cout << "Sub-array between [" << start << ", "<< start + k - 1 << "] has minimum average";
}
int main()
{
    int arr[] = {12, 34, 20, 30, 24, 45};
    int k = 3;
    int n = sizeof arr / sizeof arr[0];
    getMinimumAvgSubarray(arr, n, k);
    return 0;
}

Sub-array between [0, 2] has minimum average

Java Code

class MinimumAverageSubArray
{
    public static void getMinimumAvgSubarray(int arr[], int n, int k)
    {
        if (n < k)
            return;

        int start = 0;

        int sum = 0;
        for (int i = 0; i < k; i++)
            sum += arr[i];

        int leastSum = sum;

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

            if (sum < leastSum)
            {
                leastSum = sum;
                start = (i - k + 1);
            }
        }
        System.out.println("Subarray between [" +start + ", " + (start + k - 1) +"] has minimum average");
    }
    public static void main(String[] args)
    {
        int arr[] = {12, 34, 20, 30, 24, 45};
        int k = 3;
        getMinimumAvgSubarray(arr, arr.length, k);
    }
}

Subarray between [0, 2] has minimum average

Complexity Analysis

Time Complexity  to find the subarray with least average

O(n) where “n” is the number of elements in the array. Here we have just traversed over the array once, thus algorithm has linear time complexity.

Space Complexity to find the subarray with least average

O(n) because we used an array for storing the input but the solution uses only constant extra space.