Find subarray with given sum | Set 2 (Handles Negative Numbers)

Last Updated : 20 Sep, 2022

Given an unsorted array of integers, find a subarray that adds to a given number. If there is more than one subarray with the sum of the given number, print any of them.

Examples:

Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Output: Sum found between indexes 2 and 4
Explanation: Sum of elements between indices
2 and 4 is 20 + 3 + 10 = 33

Input: arr[] = {10, 2, -2, -20, 10}, sum = -10
Output: Sum found between indexes 0 to 3
Explanation: Sum of elements between indices
0 and 3 is 10 + 2 – 2 – 20 = -10

Input: arr[] = {-10, 0, 2, -2, -20, 10}, sum = 20
Output: No subarray with given sum exists
Explanation: There is no subarray with the given sum

Note: We have discussed a solution that does not handle negative integers here. In this post, negative integers are also handled.

Naive Approach: To solve the problem follow the below idea:

A simple solution is to consider all subarrays one by one and check the sum of every subarray. The following program implements the simple solution. Run two loops: the outer loop picks a starting point I and the inner loop tries all subarrays starting from i.

Follow the given steps to solve the problem:

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 sum to calculate the sum. For every index in the inner loop update sum = sum + array[j]If the sum is equal to the given sum then print the subarray.
For every index in the inner loop update sum = sum + array[j]
If the sum is equal to the given sum then print the subarray.

Below is the implementation of the above approach:

C++

/* A simple program to print subarray
with sum as given sum */
#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 */
int subArraySum(int arr[], int n, int sum)
{
    int curr_sum, i, j;
 
    // Pick a starting point
    for (i = 0; i < n; i++) {
        curr_sum = 0;
 
        // try all subarrays starting with 'i'
        for (j = i; j < n; j++) {
            curr_sum = curr_sum + arr[j];
 
            if (curr_sum == sum) {
                cout << "Sum found between indexes " << i
                     << " and " << j;
                return 1;
            }
        }
    }
 
    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;
 
    // Function call
    subArraySum(arr, n, sum);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG {
 
    /* Returns true if the there is a subarray
    of arr[] with sum equal to 'sum' otherwise
    returns false. Also, prints the result */
    static int subArraySum(int arr[], int n, int sum)
    {
        int curr_sum, i, j;
 
        // Pick a starting point
        for (i = 0; i < n; i++) {
            curr_sum = 0;
 
            // try all subarrays starting with 'i'
            for (j = i; j < n; j++) {
                curr_sum = curr_sum + arr[j];
 
                if (curr_sum == sum) {
                    System.out.print(
                        "Sum found between indexes " + i
                        + " and " + j);
                    return 1;
                }
            }
        }
 
        System.out.print("No subarray found");
        return 0;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
        int n = arr.length;
        int sum = 23;
 
        // Function call
        subArraySum(arr, n, sum);
    }
}
 
// This code is contributed by code_hunt.

Python3

# Python3 program to print subarray
# with sum as given sum
 
 
# Returns true if the there is a subarray
# of arr[] with sum equal to 'sum' otherwise
# returns false. Also, prints the result */
def subArraySum(arr, n, sum):
 
    # Pick a starting point
    for i in range(n):
        curr_sum = 0
        # try all subarrays starting with 'i'
        for j in range(i, n):
            curr_sum += arr[j]
            if (curr_sum == sum):
                print("Sum found between indexes", i, "and", j)
                return
 
    print("No subarray found")
 
 
# Driver Code
if __name__ == "__main__":
    arr = [15, 2, 4, 8, 9, 5, 10, 23]
    n = len(arr)
    sum = 23
 
    # Function Call
    subArraySum(arr, n, sum)
 
 
# This code is contributed by phasing17

C#

/* A simple program to print subarray
with sum as given sum */
 
using System;
 
public static class GFG {
    /* Returns true if the there is a subarray
    of arr[] with sum equal to 'sum' otherwise
    returns false. Also, prints the result */
 
    public static int subArraySum(int[] arr, int n, int sum)
    {
        int curr_sum;
        int i;
        int j;
 
        // Pick a starting point
        for (i = 0; i < n; i++) {
            curr_sum = 0;
 
            // try all subarrays starting with 'i'
            for (j = i; j < n; j++) {
                curr_sum = curr_sum + arr[j];
 
                if (curr_sum == sum) {
                    Console.Write(
                        "Sum found between indexes ");
                    Console.Write(i);
                    Console.Write(" and ");
                    Console.Write(j);
                    return 1;
                }
            }
        }
 
        Console.Write("No subarray found");
        return 0;
    }
 
    // Driver Code
    public static void Main()
    {
        int[] arr = { 15, 2, 4, 8, 9, 5, 10, 23 };
        int n = arr.Length;
        int sum = 23;
 
        // Function call
        subArraySum(arr, n, sum);
    }
}
 
// This code is contributed by Aarti_Rathi

Javascript

/* JavaScript program to print subarray
with sum as given sum */
 
  
/* Returns true if the there is a subarray
of arr[] with sum equal to 'sum' otherwise
returns false. Also, prints the result */
function subArraySum(arr, n, sum)
{
    var curr_sum, i, j;
  
    // Pick a starting point
    for (i = 0; i < n; i++) {
        curr_sum = 0;
  
        // try all subarrays starting with 'i'
        for (j = i ; j < n; j++) {
           curr_sum = curr_sum + arr[j];
           
            if (curr_sum == sum) {
                console.log("Sum found between indexes " + i + " and " + j);
                return;
            }
        }
    }
  
    console.log("No subarray found");
}
  
// Driver Code
var arr = [ 15, 2, 4, 8, 9, 5, 10, 23 ];
var n = arr.length;
var sum = 23;
 
//Function Call
subArraySum(arr, n, sum);
 
 
//This code is contributed by phasing17

Output

Sum found between indexes 1 and 4

Time Complexity: O(N²)
Auxiliary Space: O(1)

Find subarray with given sum using Hash-Map:

To solve the problem follow the below idea:

The idea is to store the sum of elements of every prefix of the array in a hashmap, i.e, every index stores the sum of elements up to that index hashmap. So to check if there is a subarray with a sum equal to s, check for every index i, and sum up to that index as x. If there is a prefix with a sum equal to (x – s), then the subarray with the given sum is found

Follow the given steps to solve the problem:

Create a Hashmap (hm) to store a key-value pair, i.e, key = prefix sum and value = its index, and a variable to store the current sum (sum = 0) and the sum of the subarray as s
Traverse through the array from start to end.
For every element update the sum, i.e sum = sum + array[i]
If the sum is equal to s then print that the subarray with the given sum is from 0 to i
If there is any key in the HashMap which is equal to sum – s then print that the subarray with the given sum is from hm[sum – s] to i
Put the sum and index in the hashmap as a key-value pair.

Dry-run of the above approach:

Below is the implementation of the above approach:

C++

// C++ program to print subarray with sum as given sum
#include <bits/stdc++.h>
using namespace std;
 
// Function to print subarray with sum as given sum
void subArraySum(int arr[], int n, int sum)
{
    // create an empty map
    unordered_map<int, int> map;
 
    // Maintains sum of elements so far
    int curr_sum = 0;
 
    for (int i = 0; i < n; i++) {
        // add current element to curr_sum
        curr_sum = curr_sum + arr[i];
 
        // if curr_sum is equal to target sum
        // we found a subarray starting from index 0
        // and ending at index i
        if (curr_sum == sum) {
            cout << "Sum found between indexes " << 0
                 << " to " << i << endl;
            return;
        }
 
        // If curr_sum - sum already exists in map
        // we have found a subarray with target sum
        if (map.find(curr_sum - sum) != map.end()) {
            cout << "Sum found between indexes "
                 << map[curr_sum - sum] + 1 << " to " << i
                 << endl;
            return;
        }
 
        map[curr_sum] = i;
    }
 
    // If we reach here, then no subarray exists
    cout << "No subarray with given sum exists";
}
 
// Driver code
int main()
{
    int arr[] = { 10, 2, -2, -20, 10 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = -10;
 
    // Function call
    subArraySum(arr, n, sum);
 
    return 0;
}

Java

// Java program to print subarray with sum as given sum
import java.util.*;
 
class GFG {
 
    public static void subArraySum(int[] arr, int n,
                                   int sum)
    {
        // cur_sum to keep track of cumulative sum till that
        // point
        int cur_sum = 0;
        int start = 0;
        int end = -1;
        HashMap<Integer, Integer> hashMap = new HashMap<>();
 
        for (int i = 0; i < n; i++) {
            cur_sum = cur_sum + arr[i];
            // check whether cur_sum - sum = 0, if 0 it
            // means the sub array is starting from index 0-
            // so stop
            if (cur_sum - sum == 0) {
                start = 0;
                end = i;
                break;
            }
            // if hashMap already has the value, means we
            // already
            // have subarray with the sum - so stop
            if (hashMap.containsKey(cur_sum - sum)) {
                start = hashMap.get(cur_sum - sum) + 1;
                end = i;
                break;
            }
            // if value is not present then add to hashmap
            hashMap.put(cur_sum, i);
        }
        // if end is -1 : means we have reached end without
        // the sum
        if (end == -1) {
            System.out.println(
                "No subarray with given sum exists");
        }
        else {
            System.out.println("Sum found between indexes "
                               + start + " to " + end);
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int[] arr = { 10, 2, -2, -20, 10 };
        int n = arr.length;
        int sum = -10;
 
        // Function call
        subArraySum(arr, n, sum);
    }
}

Python3

# Python3 program to print subarray with sum as given sum
 
# Function to print subarray with sum as given sum
 
 
def subArraySum(arr, n, Sum):
 
    # create an empty map
    Map = {}
 
    # Maintains sum of elements so far
    curr_sum = 0
 
    for i in range(0, n):
 
        # add current element to curr_sum
        curr_sum = curr_sum + arr[i]
 
        # if curr_sum is equal to target sum
        # we found a subarray starting from index 0
        # and ending at index i
        if curr_sum == Sum:
 
            print("Sum found between indexes 0 to", i)
            return
 
        # If curr_sum - sum already exists in map
        # we have found a subarray with target sum
        if (curr_sum - Sum) in Map:
 
            print("Sum found between indexes",
                  Map[curr_sum - Sum] + 1, "to", i)
 
            return
 
        Map[curr_sum] = i
 
    # If we reach here, then no subarray exists
    print("No subarray with given sum exists")
 
 
# Driver code
if __name__ == "__main__":
 
    arr = [10, 2, -2, -20, 10]
    n = len(arr)
    Sum = -10
 
    # Function call
    subArraySum(arr, n, Sum)
 
# This code is contributed by Rituraj Jain

C#

using System;
using System.Collections.Generic;
 
// C# program to print subarray with sum as given sum
 
public class GFG {
 
    public static void subArraySum(int[] arr, int n,
                                   int sum)
    {
        // cur_sum to keep track of cumulative sum till that
        // point
        int cur_sum = 0;
        int start = 0;
        int end = -1;
        Dictionary<int, int> hashMap
            = new Dictionary<int, int>();
 
        for (int i = 0; i < n; i++) {
            cur_sum = cur_sum + arr[i];
            // check whether cur_sum - sum = 0, if 0 it
            // means the sub array is starting from index 0-
            // so stop
            if (cur_sum - sum == 0) {
                start = 0;
                end = i;
                break;
            }
            // if hashMap already has the value, means we
            // already
            // have subarray with the sum - so stop
            if (hashMap.ContainsKey(cur_sum - sum)) {
                start = hashMap[cur_sum - sum] + 1;
                end = i;
                break;
            }
            // if value is not present then add to hashmap
            hashMap[cur_sum] = i;
        }
        // if end is -1 : means we have reached end without
        // the sum
        if (end == -1) {
            Console.WriteLine(
                "No subarray with given sum exists");
        }
        else {
            Console.WriteLine("Sum found between indexes "
                              + start + " to " + end);
        }
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        int[] arr = new int[] { 10, 2, -2, -20, 10 };
        int n = arr.Length;
        int sum = -10;
 
        // Function call
        subArraySum(arr, n, sum);
    }
}
 
// This code is contributed by Shrikant13

Javascript

// Javascript program to print subarray with sum as given sum
 
    function subArraySum(arr, n, sum) {
        //cur_sum to keep track of cumulative sum till that point
        let cur_sum = 0;
        let start = 0;
        let end = -1;
        let hashMap = new Map();
   
        for (let i = 0; i < n; i++) {
            cur_sum = cur_sum + arr[i];
            //check whether cur_sum - sum = 0, if 0 it means
            //the sub array is starting from index 0- so stop
            if (cur_sum - sum == 0) {
                start = 0;
                end = i;
                break;
            }
            //if hashMap already has the value, means we already 
            // have subarray with the sum - so stop
            if (hashMap.has(cur_sum - sum)) {
                start = hashMap.get(cur_sum - sum) + 1;
                end = i;
                break;
            }
            //if value is not present then add to hashmap
            hashMap.set(cur_sum, i);
   
        }
        // if end is -1 : means we have reached end without the sum
        if (end == -1) {
            console.log("No subarray with given sum exists");
        } 
        else {
            console.log("Sum found between indexes "
                            + start + " to " + end);
        }
   
    }
 
// Driver program 
 
         let arr = [10, 2, -2, -20, 10];
        let n = arr.length;
        let sum = -10;
        subArraySum(arr, n, sum);

Output

Sum found between indexes 0 to 3

Time complexity: O(N). If hashing is performed with the help of an array, then this is the time complexity. In case the elements cannot be hashed in an array a hash map can also be used as shown in the above code.
Auxiliary space: O(N). As a HashMap is needed, this takes linear space.

Related Article: Find subarray with given sum with negatives allowed in constant space

A

Aditya Goel

Improve

Previous Article

Design a data structure that supports insert, delete, search and getRandom in constant time

Implementing our Own Hash Table with Separate Chaining in Java

Similar Reads

Check if array elements are consecutive in O(n) time and O(1) space (Handles Both Positive and negative numbers)

Given an unsorted array of distinct numbers, write a function that returns true if array consists of consecutive numbers. Examples : Input : arr[] = {5, 4, 2, 1, 3} Output : Yes Input : arr[] = {2, 1, 0, -3, -1, -2} Output : YesRecommended: Please solve it on “PRACTICE ” first, before moving on to the solution. We have discussed three different app

Find Subarray with given sum | Set 1 (Non-negative Numbers)

Given an array arr[] of non-negative integers and an integer sum, find a subarray that adds up to the given sum. There may be more than one subarray with the sum equal to the given sum, but you need to print the first such subarray. Examples: Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33Output: Sum found between indexes 2 and 4Explanation: Sum of e

First subarray with negative sum from the given Array

Given an array arr[] consisting of N integers, the task is to find the start and end indices of the first subarray with a Negative Sum. Print "-1" if no such subarray exists. Note: In the case of multiple negative-sum subarrays in the given array, the first subarray refers to the subarray with the lowest starting index. Examples: Input: arr[] = {3,

Maximum sum of array after removing a positive or negative subarray

Given an array arr[] of N non-zero integers, the task is to find the maximum sum of the array by removing exactly one contiguous set of positive or negative elements. Examples: Input: arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}Output: 4Explanation: Maximum array sum can be obtained by removing subarray arr[0, 1] since arr[0, 1] has same type of elements

Largest sum contiguous subarray having only non-negative elements

Given an integer array arr[], the task is to find the largest sum contiguous subarray of non-negative elements and return its sum. Examples: Input: arr[] = {1, 4, -3, 9, 5, -6} Output: 14 Explanation: Subarray [9, 5] is the subarray having maximum sum with all non-negative elements. Input: arr[] = {12, 0, 10, 3, 11} Output: 36 Recommended PracticeM

Maximum sum subarray having sum less than given sum using Set

Given an array arr[] of length N and an integer K, the task is the find the maximum sum subarray with a sum less than K.Note: If K is less than the minimum element, then return INT_MIN. Examples: Input: arr[] = {-1, 2, 2}, K = 4 Output: 3 Explanation: The subarray with maximum sum which is less than 4 is {-1, 2, 2}. The subarray {2, 2} has maximum

Find ratio of zeroes, positive numbers and negative numbers in the Array

Given an array a of integers of size N integers, the task is to find the ratio of positive numbers, negative numbers and zeros in the array up to four decimal places. Examples: Input: a[] = {2, -1, 5, 6, 0, -3} Output: 0.5000 0.3333 0.1667 There are 3 positive, 2 negative, and 1 zero. Their ratio would be positive: 3/6 = 0.5000, negative: 2/6 = 0.3

First subarray having sum at least half the maximum sum of any subarray of size K

Given an array arr[] and an integer K, the task is to find the first subarray which has a sum greater than or equal to half of the maximum possible sum from any subarray of size K. Examples: Input: arr[] = {2, 4, 5, 1, 4, 6, 6, 2, 1, 0}, K = 3 Output: 6 2 1 Explanation: The given array has a maximum possible sum from any subarray of size K is 16 fr

Find minimum subarray sum for each index i in subarray [i, N-1]

Given an array arr[] of size N, the task is to find the minimum subarray sum in the subarrays [i, N-1] for all i in [0, N-1]. Examples: Input: arr[ ] = {3, -1, -2}Output: -3 -3 -2Explanation: For (i = 1) i.e. {3, -1, -2}, the minimum subarray sum is -3 for {-1, -2}.For (i = 2) i.e. {-1, -2}, the minimum subarray sum is -3 for {-1, -2}.For (i = 3) i

Minimum cost to convert all elements of a K-size subarray to 0 from given Ternary Array with subarray sum as cost

Given an array arr[] of N integers, where each array element is either 0, 1, or 2, and an integer K, the task is to print the minimum cost needed to convert all the elements of the array to 0s by selecting a subarray of size K and converting any array element of the subarray to 0 in one operation with the cost equal to the sum of elements of the su

Article Tags :

Arrays
DSA

Practice Tags :

Arrays