Find subarray with given sum (Non-negative Numbers)

Given a non-negative subarray of size n, we have to find the index of subarrays such that their sum is equal to the given sum k.

Note: If there may be more than one subarrays then print first such subarrays and if no such subarray exists print “There is no subarray with sum = k”

Input:  arr[] = {4, 7, 7, 2, 5, 5, 2, 3}, k = 12
Output: The subarray exists between the index 3 and 6 
Sum of elements between indices 3 & 6 
    2 + 5 + 5 = 12

Input:  arr[] = {1, 4, 7, 6, 3, 9, 5}, sum = 8
Ouptut: There is no subarray with sum 8

Naive Approach

A simple approach would be to check for all such subarrays and one by one compare the sum of the current subarray with the given sum. To implement this approach we will take two loops i & j. The outer loop i will point to the starting element of the current subarray and the inner loop will try all possible subarray starting from i.

Algorithm

for(i=0; i<n; i++)
{
    sum = 0;
    for(j=i; j<n; j++)
    {
       sum = sum + arr[j]
       if(sum == k)
           print(i,j)
    }
}

Time Complexity

The time complexity of the above approach is O(n²) because we have a nested loop to find all possible subarray.

Optimized Approach

Since we have all positive numbers in the given array, instead of finding all possible subarrays, finding their sum, and comparing with the given sum, we can use the sliding window method.

The idea here is to start with an empty subarray, add an element to it until the sum is less than the given sum. If the sum is greater than the given sum, remove the elements from the starting position from the current subarray sum until the sum doesn’t become less than or equal to the given sum k.

Algorithm

1. Create a variable sum & start and assign it to zero i.e. int sum = 0, start = 0;
2.  Traverse the array from 0 to n, where n is the size of given array arr[]
3. For each element i in range 0 to n
   1. Update the value of sum as: sum = sum + arr[i];
   2. if sum is greater than the given sum k, update the sum as sum = sum – arr[start] and increment start by 1 i.e. start = start + 1;
   3. Repeat step 3.2 until the sum is greater than k
4. If sum == k, print the subarray and break

Implementation of the above Algorithm

/*CPP code to find a
subarray with the given sum */

#include <bits/stdc++.h>
using namespace std;

int findSubarray(int *arr, int n, int k) 
{
    //initialize the variable sum and start to 0
    int sum=0, start=0;

    /*Add element one by one to the sum and
    if the sum is greater than k, then remove
    elements from the by incrementing start*/
    for(int i=0; i<n; i++)
    {
        //add current element to the sum
        sum = sum + arr[i];

        /*while sum is greater than k, remove
        elements from the sum from starting index*/
        while(sum > k)
            sum = sum - arr[start++];

        /*If current sum equals to the given sum k, then
        print the starting and the ending index of subarray*/
        if(sum == k)
        {
                cout<<"The subarray exists between "<<start<<" "<<i+1<<endl;
                return 0;
        }
                
    }

    cout<<"There is no subarray with sum ="<<k<<endl;
    return 0;
}

//Driver Code
int main() 
{

    int arr[] = {4, 7, 7, 2, 5, 5, 2, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 12;

    findSubarray(arr, n, k);
    
    return 0;
}

Output

The subarray exists between 3 6

Complexity Analysis

Time Complexity: The time complexity of the above algorithm is O(N), where N is the size of the given array because we are doing only one traversal

Space Complexity: The space complexty of the above algorithm is O(1) because we are not using any additional space here.