 # Find subarray with a sum to given number-2 | Handle negative numbers

Problem: Given an array (positive and negative) and an integer, find the subarray with sum is equal to the given integer.

Note: This problem is an extension of – find the subarray with sum to a Given Value, in which arrays with negative numbers are not handled.

Example:

```Given input: [25, 12, -14, 22, -19, 15, -10, 23]
K = -11.
Subarray with sum = -11
Output: [-14 22 -19 ]

Given input: [10, 0, -1, 20, 25, 30]
K = 45
Subarray with sum = 45
Output: [20 25]
```

Approach:

Given : input[] and K

Idea: We need to find subarray input[a, b] – sum of elements from index a to b  = K.

input[a, b] = input[0, b] – input[0, a-1]

Steps:

• Initialize a map which will store the sum up to element at the current index and current index as a value.
• Initialize i = 0, j = -1.
• Initialize curr_sum = 0, keep adding elements during iteration.
• Iterate through array and for  currenct index n,
• curr_sum = curr_sum +  input[n].
• Check if curr_sum = K, we have found a subarray and means all the elements till the current element are included, do j = n, and break the loop.
• Check if the map contains curr_sum – K, if yes then we have found a subarray, get the index from the map for key curr_sum – K and do i = index + 1 and j = n, the elements from index i to j will have sum = K.
• Check if j!=-1, means we have found the subarray during iteration. Print the elements from index i to index j. (input[i, j]), else if j==-1 then no subarray exists with sum = K.

Time Complexity: O(N), Space Complexity: O(N)

Complete Code:

Output:

```Given input: [25, 12, 14, 22, 19, 15, 10, 23]
Subarray with sum = 55
14 22 19
--------------------------------
Given input: [25, 12, -14, 22, -19, 15, -10, 23]
Subarray with sum = -11
-14 22 -19
--------------------------------
Given input: [10, 0, -1, 20, 25, 30]
Subarray with sum = 45
20 25
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.