# In an Array, find the Contiguous Subarray with Sum to a Given Value.

Objec­tive: Given an array and an inte­ger, find the Sub­ar­ray whose sum is equal to the given integer.

Exam­ples:

```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 Com­plex­ity — O(n2).

Bet­ter Approach: Time Com­plex­ity — O(n)

• Idea is to keep adding all the ele­ments to the currSum
• Keep check­ing if the currSum<Sum
• If currSum gets greater than the Sum then start reduc­ing the currSum from the begin­ning of the array using “start“if any time currSum=Sum, Stop and return

NOTE: Tech­nique used in this prob­lem can be used to solve the prob­lem “Find a sub­ar­ray such that the sum of ele­ments in it is equal to zero”. In that the array will aldo have to con­tain the neg­a­tive ele­ments and our given sum is zero.

Com­plete Code:

Out­put:

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

```

#### You may also like...

• Deep Shah

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

• tuto­ri­al­hori­zon

Yes it can be, but the solu­tion pro­vided is also O(n).

• Deep Shah

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

pri­vate sta­tic int maxSubarray(int[] arr) {

// TODO Auto-generated method stub

int max_sum = 0;

int sum = 0;

int startIn­dex = 0; // intially start index is at 0

int endIn­dex = 0; // intially end index is at 0 position

int temp­Start = 0; // intially start = temp­start = 0

if(arr.length == 0){

System.out.println(“No Ele­ments in Array”);

return –1;

}

else if(arr.length == 1){

System.out.println(“Array con­tains only sin­gle element”);

startIn­dex = 0;

endIn­dex = 0;

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

return arr[0];

}

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

sum = sum + arr[i];

if(max_sum < sum){

max_sum = sum;

startIn­dex = temp­Start; // max_sum < sum so we found a greater sum from last temp­start to cur­rent element

endIn­dex = i; // make end as cur­rent element

}

else if(sum < 0){

sum = 0;

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

}

}

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

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

for(int i = startIn­dex; i<= endIndex;i++){

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

}

return max_sum;

}

• Holden

Have you solved this prob­lem with Kandane’s algo­rithm? Could you please write your code in Ideone and share its link here?
Since it is not read­able here.

• Holden

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++) {

?

• Holden

There is a while in ‘for’ loop, is it still O(n) solu­tion? Your pro­posed logic seems lin­ear; But in text­books, we read if there is two nested loop, time com­plex­ity will be quadratic.

• Holden

I think I got it! These 2 loops are inde­pen­dent! If two loops are not inde­pen­dent, time com­plex­ity will be O(n^2). Thank you

• tuto­ri­al­hori­zon

Yes holden you got it right. Though there are two nested loops but still every ele­ment will be tra­versed only once.

• jafar basha

In an Array, find the Small­est Con­tigu­ous Sub­ar­ray with Sum to a Given Value.
https://github.com/jafar9/c-prg/blob/master/smallestsubarray.c