Home » Technical Interview Questions » Array Interview Questions » Subarray with Given Sum

Subarray with Given Sum


In the subarray with the given sum problem, we have given an array containing n positive elements. We have to find the subarray in which the sum of all the elements of subarray equal to a given_sum. Subarray is obtained from the original array by deleting some elements from the starting or end of the array.

Example

a. Input array be: [1, 3, 7, 9, 11, 15, 8, 6]

Sum = 19
Output will be: 1 and 3 → [3, 7, 9], subarray sum = 19

b. Input array be: [1, 3, 7, 9, 11, 15, 8, 6]

Sum = 20
Output will be: 0 and 3 → [1, 3, 7, 9], subarray sum = 20

c. Input array be: [1, 3, 7, 9, 11, 15, 8, 6]

Sum = 40
Output will be: No subarray with given sum found.

d. Input array be: [4, 3, 2, 8, 9, 11]

Sum = 8
Output will be: 3 and 3 → [8], subarray sum = 8

Approach 1

Algorithm

Consider all subarrays and check the sum of every subarray.

  1. Run two loops.
  2. Outer loop pics the start index.
  3. The inner loop finds all subarrays and finds the sum.
  4. If sum = current_sum, current_sum is the sum of the present subarray, print start, and end indexes.

C++ Program for Subarray with Given Sum

#include <bits/stdc++.h>
using namespace std;
int SubarraySum(int array[], int N, int sum)
{
    int current_sum, i, j;
    //i is start point and j - 1 is end point
    for (i = 0; i < N; i++)
    {
        current_sum = array[i];
        for (j = i+1; j < N + 1; j++)
        {
            if (current_sum == sum)
            {
                cout<<"Subarray with given sum is between indexes "<<i<<" and "<<j-1<<endl; 
                return 1;
            }
            else if (current_sum > sum)
            {
                break;
            }
           current_sum = current_sum + array[j];
        }
    }
    cout<<"No subarray found with given sum"<<endl;
    return 0;
}
 
//Main function
int main()
{
    int input_array[] = {1,3, 8, 9,11, 13, 17, 21};
    int N = sizeof(input_array)/sizeof(input_array[0]);
    int Sum = 28;
    SubarraySum(input_array,N,Sum);
    return 0;
}
Subarray with given sum is between indexes 2 and 4

Approach 2

Algorithm

Create a subarray sum function that takes the array and sum as an argument and gives start and end indexes of the subarray with a given sum.

  1. First Initialize current_sum as the first element of the array and store start index as 0.
  2. If current_sum exceeds sum, remove staring element and increment start index.
  3. If current_sum equals sum then returns the start and end indexes.
  4. Add elements to the current_sum one by one.
  5. If loop ends then print “No subarray found with given_sum.”

C++ Program for Subarray with Given Sum

#include <bits/stdc++.h>
using namespace std;
int SubarrySum(int array[], int n, int sum)
{
    //Initialize current_sum = first element.Therefore, start_index =0
    int current_sum = array[0];
    int start_index = 0;
    
    //if current_sum > sum remove last element
    for(int i = 1; i <= n; i++)
    {
        while(current_sum > sum && start_index < i-1)
        {
            current_sum = current_sum - array[start_index];
            start_index++;
        }
        if(current_sum == sum)
        {
            cout<<"Subarray with given sum is between indexes "<<start_index<<" and "<<i-1<<endl;
            return 1;
        }
        //Add current element to current_sum
        if(i < n)
        {
          current_sum = current_sum + array[i];
        }
    }
    cout<<"No subarray found with given sum"<<endl;
    return 0;
}
 
//Main function
int main()
{
    int input_array[] = {1,3, 8, 9,11, 13, 17, 21};
    int N = sizeof(input_array)/sizeof(input_array[0]);
    int Sum = 28;
    SubarrySum(input_array,N,Sum);
    return 0;
}
Subarray with given sum is between indexes 2 and 4

Complexity Analysis

Time complexity

O(n*n) where n is the size of the given array. Here we traverse the array one time and check for the conditions.

Space Complexity

O(1) because we don’t use any auxiliary space here.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup