Finding SubArray with Given Sum

In this article, we are going to discuss a very famous question from an interview perspective called subarray with given sum.

How to Find SubArray with Given Sum:

This problem is also known as subarray sum equals k. Given an array of non-negative integers and an integer sum, find a subarray that adds to a given sum.

Note: There may be more than one subarray with sum as the given sum, print first such subarray.

Examples:

Input: arr[] = [ 1, 20, 3, 10, 5 ], sum = 33

Output:

Sum found between indexes 1 and 3

Explanation:
Sum of elements between indices 1 and 3 is 20 + 3 + 10 = 33

Input:

arr[] = [1, 4, 0, 0, 3, 10, 5], sum = 7

Output:

Sum found between indexes 1 and 4

Explanation:
Sum of elements between indices 1 and 4 is 4 + 0 + 0 + 3 = 7

Input:

arr[] = [ 1, 4 ], sum = 0

Output:

No subarray found

Explanation:
There is no subarray with 0 sum

Approach 1 to Find SubArray with Given Sum

Find subarray with given sum using Nested loop
The idea behind this approach is to consider all subarrays of the given array one by one and check the sum of every subarray.

Algorithm:
Run two loops: the outer loop picks a starting point i and the inner loop tries all subarrays starting from j.

Follow the steps given below to implement the approach:

  • Traverse the array from start to end.
  • From every index start another loop from i to the end of the array to get all subarrays starting from i, and keep a variable currentSum to calculate the sum of every subarray.
  • For every index in inner loop update currentSum = currentSum + arr[j]
  • If the currentSum is equal to the given sum then print the subarray.

Below is the implementation of the above approach.

#include <bits/stdc++.h>
using namespace std;
 
/* Returns true if the there is a subarray
of arr[] with sum equal to 'sum' otherwise
returns false. Also, prints the result */
void subArraySum(int arr[], int n, int sum)
{
 
    // Pick a starting point
    for (int i = 0; i < n; i++) {
        int currentSum = arr[i];
 
        if (currentSum == sum) {
            cout << "Sum found at indexes " << i << endl;
            return;
        }
        else {
            // Try all subarrays starting with 'i'
            for (int j = i + 1; j < n; j++) {
                currentSum += arr[j];
 
                if (currentSum == sum) {
                    cout << "Sum found between indexes "
                         << i << " and " << j << endl;
                    return;
                }
            }
        }
    }
    cout << "No subarray found";
    return;
}
 
// Driver Code
int main()
{
    int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 23;
    subArraySum(arr, n, sum);
    return 0;
}

Output:

Sum found between indexes 1 and 4

Time Complexity: O(N2), Trying all subarrays from every index, used nested loop for the same

Auxiliary Space: O(1).

Approach 2 to Find SubArray With Given Sum

Find subarray with given sum using sliding window technique
The idea is simple as we know that all the elements in subarray are positive so, If a subarray has sum greater than the given sum then there is no possibility that adding elements to the current subarray will be equal to the given sum. So the Idea is to use a similar approach to a sliding window technique.

Algorithm:
Step 1: Start with an empty subarray
Step 2: add elements to the subarray until the sum is less than x( given sum ).
Step 3: If the sum is greater than x, remove elements from the start of the current subarray.

Follow the steps given below to implement the approach:

  • Create two variables, start=0, currentSum = arr[0]
  • Traverse the array from index 1 to end.
  • Update the variable currentSum by adding current element, currentSum = currentSum + arr[i]
  • If the currentSum is greater than the given sum, update the variable currentSum as currentSum = currentSum – arr[start],
    and update start as, start++.
  • If the currentSum is equal to given sum, print the subarray and break the loop.

Below is the implementation of the above approach.

Subarray with given sum 2

#include <iostream>
using namespace std;
 
/* Returns true if the there is a subarray of
arr[] with a sum equal to 'sum' otherwise
returns false. Also, prints the result */
int subArraySum(int arr[], int n, int sum)
{
    /* Initialize currentSum as value of
    first element and starting point as 0 */
    int currentSum = arr[0], start = 0, i;
 
    /* Add elements one by one to currentSum and
    if the currentSum exceeds the sum,
    then remove starting element */
    for (i = 1; i <= n; i++) {
        // If currentSum exceeds the sum,
        // then remove the starting elements
        while (currentSum > sum && start < i - 1) {
            currentSum = currentSum - arr[start];
            start++;
        }
 
        // If currentSum becomes equal to sum,
        // then return true
        if (currentSum == sum) {
            cout << "Sum found between indexes " << start
                 << " and " << i - 1;
            return 1;
        }
 
        // Add this element to currentSum
        if (i < n)
            currentSum = currentSum + arr[i];
    }
 
    // If we reach here, then no subarray
    cout << "No subarray found";
    return 0;
}
 
// Driver Code
int main()
{
    int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 23;
    subArraySum(arr, n, sum);
    return 0;
}

Output:

Sum found between indexes 1 and 4

Time Complexity: O(N)
Auxiliary Space: O(1). Since no extra space has been taken.

Finally, we optimized our code and reduced our time complexity from O(N2) to O(N).

Leave a Reply

Your email address will not be published. Required fields are marked *