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

Find the maximum sum of all the possible subarrays of length k=3 in O(n) time for the array:

    {2, 5, -4, 0, 7, -1, 9, 6, 7, 2}

Assume that k is less than n.

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 is obtained and compared with the previous sub-array sum.

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

Brute-Force Program for Maximum Sum in O(k x n) Time

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

#include <stdio.h>

int maxSumBrute(int A[], int n, int k){
    // Initialize answer
    int maxSum = -4*k;

    // 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;
    }

    return maxSum;
}

int main(int argc, char **argv) {
    int A[] = {2, 5, -4, 0, 7, -1, 9, 6, 7, 2};
    int k = 3;
    int n = sizeof(A) / sizeof(A[0]);
    
    int ret = maxSumBrute(A, n, k);
    printf("%i\n", ret);
        
    return 0;
}

The output is:

   22

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 constant O(1) times for statements such as "maxSum = sum;" are ignored, both for the actual and official time complexity quotations.

The space complexity is O(n) for the same array in the calling and called functions. The constant O(1) spaces for statements such as "maxSum = sum;" are ignored in space complexity quotation.

Smart Approach in O(n) Time

The smart approach uses a sliding window of size (length) k=3. Sliding window is sliding subarray.

- Compute the sum of the first k numbers, out of the n array 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 value.

Before the algorithm starts, the minimum sub-array sum has to be determined. This time it is 0, as the sum of the first k numbers have to be determined, first.

Smart Program for Maximum Sum

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

#include <stdio.h>

int maxSumSmart(int A[], int n, int k){
    // Initialize answer
    int maxSum = 0;

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

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

    return maxSum;
}

int main(int argc, char **argv) {
    int A[] = {2, 5, -4, 0, 7, -1, 9, 6, 7, 2};
    int k = 3;
    int n = sizeof(A) / sizeof(A[0]);
    
    int ret = maxSumSmart(A, n, k);
    printf("%i\n", ret);
        
    return 0;
}

The output is:

    22

The time complexity is O(n) for the two consecutive loops. The constant O(1) times for statements such as "maxSum = windowSum" are ignored

The space complexity is O(n) for the same array in the calling and called functions. The constant O(1) spaces for statements such as "maxSum = windowSum" are ignored.

Remember, time and space complexities are maximum estimates. They are not necessarily the correct number of operations or locations respectively.

Minimum Sum of a Subarray with K Numbers in C

The brute force approach for minimum sum is fundamentally the same as for maximum sum.

The smart approach for minimum sum is almost the same as for maximum sum, except that the following code segment for maximum sum:

        if (windowSum > maxSum) 
            maxSum = windowSum;

is changed to:

        if (windowSum < minSum)
            minSum = windowSum;

Smart Program for Minimum Sum in O(n) Time

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

#include <stdio.h>

int minSumSmart(int A[], int n, int k){
    // Initialize answer
    int minSum = 0;

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

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

    return minSum;
}

int main(int argc, char **argv) {
    int A[] = {2, 5, -4, 0, 7, -1, 9, 6, 7, 2};
    int k = 3;
    int n = sizeof(A) / sizeof(A[0]);
    
    int ret = minSumSmart(A, n, k);
    printf("%i\n", ret);
        
    return 0;
}

The output is:

    1

The time complexity is O(n) for the two consecutive loops. The constant O(1) times for statements such as "minSum = windowSum" are ignored.

The space complexity is O(n) for the same array in the calling and called functions. The constant O(1) spaces for statements such as "minSum = windowSum" are ignored.

Thanks for reading.