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

This video is contributed by Shubham Kumar

Please Like, Comment and Share the Video among your friends.

Also, Subscribe if you haven't already! :)

[anjurawat]

there is no sense of making video you just doing reading that is written on site we want more that's why we are here

[FoodMania]

I came here for understanding subarray problems with given sum, now I understood the concepts.

[spicytuna]

it seems to be working magically. i don't see the logic behind how this would work!!! thanks

[shashwatkatiyar]

what is the reason for applying the condition, start < i-1 in (cur_sum>sum && start < i-1)

[dhyeyrajveer]

If we dont want j=n, then why write the condition of j to be equal to n in for loop

[siddhantsingh]

I have a question? Why this is O(n) and not greater than O(n) because for each 'n' we may or may not going in the while loop, so doesn't that time spent in while loop adds to the time complexit

[Trading_Content]

By just your way of explaining i understand the whole concept, thankyou...

[sureshsingam]

Can you plzz tell me why we iterating for loop till n, if I try iterate till <n It's showing error, why should we iterate till less than n.

[justinmiller]

The second implementation is O(n^2) in the worst case.

The O(n) answer is to:
1- convert the input array to a sums array, s: s[i] = sum(a[0..i])
2- put the sums in a hashMap (maps sum to index)
3- iterate over the hashMap and see if the other required sumValue exists

[prateekchaplot]

If ip: 9, 2, 1, 11
The 2nd implementation fails..

Please rectify the implementation!

[tusharvaish]

I am dumb, i am unable to understand this proble ! .
I am quitting coding today

[SaddamKhan-qmim]

What if there are multiple occurrences of same repeated sub array?
What if there exist another sub array later in the sequence whose sum is equal to specifed value and length is lower i.e. for sum of 7 there may exist a array {1, 0, 0, 3, 3, 6, 9, 4, 3}, then here {4, 3} will be skipped and {1, 0, 0, 3, 3} will be returned using above code?

[ashigupta]

This is supposed to be solved by backtracking or dynamic programming

[sagarsakre]

Shouldn't the title be renamed to "Find 'contiguous' subarray with given sum?"