The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

A Subarray

A subarray is a continuous part of an array. In other-words, a subarray is an array that is inside another array.

In general, for an array of size n, there are n*(n+1)/2 non-empty subarrays.

For example, in the array [1, 2, 3, 4], there are 10 non-empty sub-arrays, which are:

[1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3], [2,3,4], and [1,2,3,4]

Two Pointers Technique

Two pointers refer to left (i) and right (j) indexes, such that left points to the start of the array and right points to the end of the array, initially. The opposite pointers move towards the center of the array during iterations, until a condition is met.

A Sliding Window

A sliding window is a sub-array that moves from one end of the array to the other end, one element at a time. The left end of the window is typically identified by the variable, i or left or back. The right end of the window is typically identified by the variable, j or right or front.

As the window moves, its size (length) may be fixed or variable. This module of the full course deals only with fixed size windows. With fixed size window, the size of the last window can be less than the size of each of the previous windows.

The sliding window is a specialized application of the two-pointers technique.

Problem

You are given an integer array A 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: A = [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: A = [5] 
k = 1
Output: 5.00000

Constraints:

n == A.length (length of array)
1 <= k <= n <= 105
-104 <= nums[i] <= 104

Note:

When a low precision like 10-5 is required, make sure all divisors are of type double, and the return type of the function, is double. Comparison is also done with doubles, or if possible, compare the sums.

Then, approach this problem as you would approach maximum subarray, but for average this time.

Brute Force (Naive) Approach in (k x n) Time

The brute-force approach was not asked for. However, it is good to know it and its limitations before embarking on the O(n) time smart approach.

In the brute force approach, there are two loops: an outer and an inner-loop. The outer loop iterates over the whole array until index n-k. The inner loop iterates over each sub-array, and at the end of a subarray scan, the subarray sum and average (divided by k of double) is obtained, and compared with the previous sub-array average.

Before the algorithm starts, the minimum possible sub-array sum and average, have to be determined, thus: Look for the smallest element in the list, -6 in the above first example, and multiply it by k (4 in the first example above). As the algorithm continues, any other average has to be greater than this minimum average, in order to obtain the maximum average, at the end.

Brute-Force Program for Maximum Sum Average

The brute-force program is (read through the code and comments):

#include <stdio.h>

double maxAvgBrute(int A[], int n, double k){
    // Initialize answer
    double maxAvg = -6*k / k;    //equal to -6.000000 and serve for both test cases
    int kInteger = k;
    int maxSum = -6 * kInteger;

    // Consider all blocks starting with i.
    for (int i = 0; i <= n - k; i++) {
        int sum = 0;
        for (int j = 0; j < k; j++) {
            sum = sum + A[i + j];
        }
        if (sum > maxSum) {
            maxSum = sum;
            maxAvg = maxSum / k ;
        }
    }

    return maxAvg;
}

int main(int argc, char **argv) {
    int A[] = {1, 12, -5, -6, 50, 3};
    double k = 4;
    int n = sizeof(A) / sizeof(A[0]);
    
    double ret = maxAvgBrute(A, n, k);
    printf("%lf\n", ret);
    
    
    int A2[] = {5};
    double k2 = 1;
    int n2 = sizeof(A2) / sizeof(A2[0]);
    
    double ret2 = maxAvgBrute(A2, n2, k2);
    printf("%lf\n", ret2);
        
    return 0;
}

The output is:

    12.750000
    5.000000

The time complexity is actually O(n-k x k) for the number of inner loop iterations multiplied by the number of outer loop iterations. Since it is the maximum of this quantity that has to be chosen, the official time complexity is O(n x k). The space complexity is O(n) for the array in the calling and called functions.

Smart Approach in O(n) Time

The smart approach uses a sliding window of size (length) k=4 (for the first example). Sliding window is sliding subarray.

- Compute the sum of the first k numbers, out of the array n numbers, and store the sum in the variable, windowSum.
- Then continue to traverse linearly over the array, in one loop, till the end of the array.
- As the window shifts, one element to the right, to obtain the current window sum, subtract the first element of the previous window position from windowSum, and add the last element of the new window position, to windowSum. The window shifts by one element at a time.
- Be doing comparison of the new windowSum with the previous windowSum to obtain the maximum sum.
- Each time a maximum sum is obtained, do the average.

Before the algorithm starts, the minimum sub-array sum and average, have to be determined. This time it is 0.

Smart Program for Maximum Sum

The smart program is (read through the code and comments):

#include <stdio.h>

double maxAvgSmart(int A[], int n, double k){
    // Initialize maxAvg and maxSum
    double maxAvg = -6*k / k;    //equal to -6.000000 and serve for both test cases
    int kInteger = k;
    int maxSum = 0;

    //the first k sum
    for (int i = 0; i < kInteger; i++)
        maxSum = maxSum + A[i];

    int windowSum = maxSum;
    if (k == n) {    //edge case, when k=n
        maxAvg = maxSum / k ;
        return maxAvg;
    }

    // Address sums and averages of remaining windows
    for (int i = k; i < n; i++) {
        windowSum = windowSum - A[i - kInteger] + A[i];
        if (windowSum > maxSum) {    //done within the single for-loop
            maxSum = windowSum;
            maxAvg = maxSum / k ;
        }
    }

    return maxAvg;
}

int main(int argc, char **argv) {
    int A[] = {1, 12, -5, -6, 50, 3};
    double k = 4;
    int n = sizeof(A) / sizeof(A[0]);
    
    double ret = maxAvgSmart(A, n, k);
    printf("%lf\n", ret);
    
    
    int A2[] = {5};
    double k2 = 1;
    int n2 = sizeof(A2) / sizeof(A2[0]);
    
    double ret2 = maxAvgSmart(A2, n2, k2);
    printf("%lf\n", ret2);
        
    return 0;
}

The output is:

    12.750000
    5.000000

The time complexity is O(n) for the two consecutive loops. The space complexity is O(n) for the same array in the calling and called functions.

Thanks for reading.