Subarray with Given Sum


Difficulty Level Medium
Frequently asked in Adobe Amazon American Express Apple Bloomberg ByteDance Coupang eBay Facebook Goldman Sachs Google LinkedIn Microsoft Oracle Quera Twilio Uber Wish Yahoo Yandex
Array Hash Hashing

Problem Statement

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 the 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.

Implementation

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 n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int sum;
    cin>>sum;
    SubarraySum(a,n,sum);
    return 0;
}

Java Program for Subarray with Given Sum

import java.util.Scanner;
class sum
{
    public static 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)
                {
                    System.out.println("Subarray with given sum is between indexes " + i + " and " + (j-1)); 
                    return 1;
                }
                else if (current_sum > sum)
                {
                    break;
                }
               current_sum = current_sum + array[j];
            }
        }
        System.out.println("No subarray found with given sum");
        return 0;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int sum;
        sum = sr.nextInt();
        SubarraySum(a,n,sum);
    }
}
8
1 3 8 9 11 13 17 21
28
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 fix starting point (i) of the subarray and calculate the sum of all the possible subarray ending at j.

Space Complexity

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

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.”

Implementation for Subarray with Given Sum

C++ Program

#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 n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int sum;
    cin>>sum;
    SubarrySum(a,n,sum);
    return 0;
}

Java Program

import java.util.Scanner;
class sum
{
    public static int SubarraySum(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)
            {
                System.out.println("Subarray with given sum is between indexes " + start_index + " and " + (i-1)); 
                return 1;
            }
            //Add current element to current_sum
            if(i < n)
            {
              current_sum = current_sum + array[i];
            }
        }
        System.out.println("No subarray found with given sum");
        return 0;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int sum;
        sum = sr.nextInt();
        SubarraySum(a,n,sum);
    }
}
6
10 6 8 4 3 8
34
No subarray found with given sum

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