Find subarray with given sum (Handles Negative Numbers)

The problem “Find subarray with given sum (Handles Negative Numbers)” states that you are given an integer array, containing negative integers as well and a number called “sum”. The problem statement asks to print the sub-array, which sums up to a given number called “sum”.  If more than one sub-array is present as our output, print any one of them.

Example

arr[] = {2,4,-2,3,1}
sum = 1

Sum found between index 2 to index 3

arr[] = {12,10,-20,30,1}
sum = 20

Sum found between index 1 to index 3

arr[] = {2,4,-2,3,1}
sum = -1

No such sub-array exists.

Algorithm

1. Declare a map.
2. Set currentSum to 0.
3. Traverse the array, while i < n,
   1. Sums up the value of currentSum and array element and store it to currentSum.
   2. Check if currentSum is equal to the sum.
      • If true, then print the index as 0 to i and break.
   3. Check if the map contains the value currentSum-sum.
      • If true then print the indexes as map’s currentSum value to i and break.
   4. If any of the given condition doesn’t satisfy, means we found nothing with the given sum.

Explanation

We are given a problem statement that asks to find out the sub-array which sums up to the given sum and if there is more than one sub-array found, then print any one of them. We are going to use HashMap and we are going to store the value of the currentSum and its index if none of the conditions satisfied after adding up each element of array and currentSum (which was initialized as a 0 earlier).

Let us consider an example:

Example

arr[] = {14, 1, -10, 20, 1}, sum=5

We have given an integer array which is containing some negative integers as well and a number sum. We have to find out the sub-array which adds up to the given number, sum. While traversing the whole array we should maintain our currentSum, this is, that gives us the possible sub-array.

i=0, currentSum=0

currentSum = currentSum + arr [i] =>currentSum=14, now we have 14 in our currentSum ,we will check if it is equal to the given sum that is 5, and that is false, then we will check if map contains the currentSum-sum that means 14-5 =9 is also false. So we will go through the next element. So we add the currentSum and i into the map.

i=1, currentSum=14

currentSum = currentSum + arr[i] => 14+1 =15, currentSum=15, now we have 15 in our currentSum, we will check if it is equal to the given sum but it does not satisfied, we will go for if map contains currentSum-sum that is 15-5-10 is also false. So we add the currentSum and i into the map.

i=2, currentSum=15,

currentSum = currentSum + arr[i] =>15 + (-10), currentSum=5, now we have 15 in our currentSum, we will check if it is equal to the given sum that is 5, and we found that the condition is satisfied,  means we got our output, then we will print the indexes of subarray 0 to i.

Code

C++ code to find subarray with given sum (Handles Negative Numbers)

#include<iostream>
#include<unordered_map>

using namespace std;

void getSubArray(int arr[], int n, int sum)
{
    unordered_map<int, int> map;
    int currentSum = 0;
    for (int i = 0; i < n; i++)
    {
        currentSum = currentSum + arr[i];
        if (currentSum == sum)
        {
            cout << "Sum found between index "<< 0 << " to index " << i << endl;
            return;
        }
        if (map.find(currentSum - sum) != map.end())
        {
            cout << "Sum found between index "<< map[currentSum - sum] + 1 << " to index " << i << endl;
            return;
        }
        map[currentSum] = i;
    }
    cout << " No such sub-array exists ";
}
int main()
{
    int arr[] = {14, 1, -10, 20, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    int sum = 5;
    getSubArray(arr, n, sum);
    return 0;
}

Sum found between index 0 to index 2

Java code to find subarray with given sum (Handles Negative Numbers)

import java.util.HashMap;

class printSubArraywithGivenSum
{
    public static void getSubArray(int[] arr, int n, int sum)
    {
        int currentSum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < n; i++)
        {
            currentSum = currentSum + arr[i];
            if (currentSum - sum == 0)
            {
                System.out.println("Sum found between index "+ 0 + " to index " + i);
                return;
            }
            if (map.containsKey(currentSum - sum))
            {
                int val=map.get(currentSum-sum)+1;
                System.out.println("Sum found between index "+ val+" to index " + i);
                return;
            }
            map.put(currentSum, i);
        }
        System.out.println("No such sub-array exists");
    }
    public static void main(String[] args)
    {
        int[] arr = {14, 1, -10, -20, 2};
        int n = arr.length;
        int sum = 5;
        getSubArray(arr, n, sum);
    }
}

Sum found between index 0 to index 2

Complexity Analysis

Time Complexity

O(N) where “N” is the number of elements in the array.

Space Complexity

O(N) where “N” is the number of elements in the array.