# Find the subarray with sum to a Given Value.

Objective: Given an array (non-negative) and an integer, Find the Subarray whose sum is equal to the given integer.

Examples:

```int[] arrA = { 25, 12, 14, 22, 19, 15, 10, 23 };
Integer = 55
Output : 55 is found between indexes 2 and 4
And Elements are : 14 22 19
```

Approach :

Naive Approach: Use 2 loops . Time Complexity – O(n2).

Better Approach: Time Complexity – O(n)

• Idea is to keep adding all the elements to the currSum
• Keep checking if the currSum<Sum
• If currSum gets greater than the Sum then start reducing the currSum from the beginning of the array using “start”if any time currSum=Sum, Stop and return

Complete Code:

Output:

```55 is found between indexes 2 and 4
And Elements are :  14 22 19

```

__________________________________________________
Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

### 9 Responses

1. Deep Shah says:

I think it can be done in O(n) time using Kadane’s Algorithm (http://en.wikipedia.org/wiki/Maximum_subarray_problem)

• tutorialhorizon says:

Yes it can be, but the solution provided is also O(n).

• Deep Shah says:

This is the other solution which I thought of . It uses only one for loop. and no nested loops inside.

private static int maxSubarray(int[] arr) {

// TODO Auto-generated method stub

int max_sum = 0;

int sum = 0;

int startIndex = 0; // intially start index is at 0

int endIndex = 0; // intially end index is at 0 position

int tempStart = 0; // intially start = tempstart = 0

if(arr.length == 0){

System.out.println(“No Elements in Array”);

return -1;

}

else if(arr.length == 1){

System.out.println(“Array contains only single element”);

startIndex = 0;

endIndex = 0;

System.out.println(“Start Index : “+startIndex + “t End Index :”+endIndex);

return arr;

}

for(int i = 0; i<arr.length;i++){

sum = sum + arr[i];

if(max_sum < sum){

max_sum = sum;

startIndex = tempStart; // max_sum < sum so we found a greater sum from last tempstart to current element

endIndex = i; // make end as current element

}

else if(sum < 0){

sum = 0;

tempStart = i + 1; // if sum is less than 0, make a fresh start with right element

}

}

System.out.println("Start Index : "+startIndex + "t End Index :"+endIndex);

System.out.print("Largest Sum is obtained from : ");

for(int i = startIndex; i<= endIndex;i++){

System.out.print(arr[i]+", ");

}

return max_sum;

}

• Holden says:

Have you solved this problem with Kandane’s algorithm? Could you please write your code in Ideone and share its link here?
Since it is not readable here.

2. Holden says:

Thank you for the great post.

Don’t you think this ‘for’:

for (int i = 0; i <= arrA.length; i++) {

should be:

for (int i = 0; i < arrA.length; i++) {

?

3. Holden says:

There is a while in ‘for’ loop, is it still O(n) solution? Your proposed logic seems linear; But in textbooks, we read if there is two nested loop, time complexity will be quadratic.

• Holden says:

I think I got it! These 2 loops are independent! If two loops are not independent, time complexity will be O(n^2). Thank you

• tutorialhorizon says:

Yes holden you got it right. Though there are two nested loops but still every element will be traversed only once.

4. jafar basha says:

In an Array, find the Smallest Contiguous Subarray with Sum to a Given Value.
https://github.com/jafar9/c-prg/blob/master/smallestsubarray.c

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