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

Given an array A[], an integer k and a Sum. The task is to check if there exists any subarray with k elements whose sum is equal to the given sum. If any of the subarray with size k has the sum equal to the given sum, print YES, otherwise print NO. Use an efficient algorithm. In your solution, make sure k is less than or equal to n, the number of elements in the array.

Examples:

Input: A[] = {1, 4, 2, 10, 2, 3, 2, 0, 20}
k = 4
sum = 18
Output: YES

Subarray = {4, 2, 10, 2}

Input: A[] = {1, 4, 2, 10, 2, 3, 2, 0, 20}
k = 3 
sum = 6
Output: No

Note:

Once the first sub-array is seen, the called function can return.

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, its subarray sum is compared with the given sub-array sum. If they are the same, 1 is returned for Yes.

By the time the iterations reach the end of the array, and no equal sub-array is found, 0 is returned for No. This is handled by "return 0;" at the end of the called function.

Brute-Force Program

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

#include <stdio.h>

int checkSubarraySumBrute(int A[], int n, int k, int givenSum) {
    //k has to be less than or equal to n
    if (!(k <= n)) 
        return -1;

    // 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 (givenSum == sum)
            return 1;
    }

    return 0;
}

int main(int argc, char **argv) {
    int A[] = {1, 4, 2, 10, 2, 3, 2, 0, 20};
    
    int k = 4;
    int givenSum = 18;
    int n = sizeof(A) / sizeof(A[0]);
    
    int ret = checkSubarraySumBrute(A, n, k, givenSum);
    if (ret == -1)
        printf("k is greater than n, and not correct\n");
    else if (ret == 1)
        printf("Yes\n");
    else if (ret == 0)
        printf("No\n");

    int k2 = 3;
    int givenSum2 = 6;
    int n2 = sizeof(A) / sizeof(A[0]);
    
    int ret2 = checkSubarraySumBrute(A, n, k, givenSum2);
    if (ret2 == -1)
        printf("k is greater than n, and not correct\n");
    else if (ret2 == 1)
        printf("Yes\n");
    else if (ret2 == 0)
        printf("No\n");
        
    return 0;
}

The output is:

    Yes
    No

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 same array in the calling and called functions.

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 whole 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 given sum to check for equality.

If k is not less than or equal to n, -1 is returned by the called function. If equality is found, 1 is returned. If equality is not found, 0 is returned. This is handled by "return 0;" at the end of the called function.

Smart Program

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

#include <stdio.h>

int checkSubarraySumSmart(int A[], int n, int k, int givenSum) {
    //k has to be less than or equal to n
    if (!(k <= n)) 
        return -1;
        
    //the first k sum
    int windowSum = 0; 
    for (int i = 0; i < k; i++)
        windowSum = windowSum + A[i];

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

    return 0;
}

int main(int argc, char **argv) {
    int A[] = {1, 4, 2, 10, 2, 3, 2, 0, 20};
    
    int k = 4;
    int givenSum = 18;
    int n = sizeof(A) / sizeof(A[0]);
    
    int ret = checkSubarraySumSmart(A, n, k, givenSum);
    if (ret == -1)
        printf("k is greater than n, and not correct\n");
    else if (ret == 1)
        printf("Yes\n");
    else if (ret == 0)
        printf("No\n");

    int k2 = 3;
    int givenSum2 = 6;
    int n2 = sizeof(A) / sizeof(A[0]);
    
    int ret2 = checkSubarraySumSmart(A, n, k, givenSum2);
    if (ret2 == -1)
        printf("k is greater than n, and not correct\n");
    else if (ret2 == 1)
        printf("Yes\n");
    else if (ret2 == 0)
        printf("No\n");
        
    return 0;
}

The output is:

    Yes
    No

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.