Array - 26: Find Sub-array whose sum is equal to given sum

Solution - 1: When you've all positive numbers
- We take two variable start & end which're pointing to starting element
- We take another variable window_sum = 0
- Now start from 1st element & add into window_sum
- If window_sum == given_sum, then we've got our sybarray
- If window_sum is less than given-sum then keep on adding element
- If window_sum is greater than given-sum then we decrease the element from the starting
- whenever you window_sum == sum, print start & end index

Time Complexity: O(n)
Space Complexity: O(1)

Solution - 2: For any case
- We take variable end which're pointing to starting element
- We take another variable total_sum_till_here = 0 & a map where key'll store total_sum_till_here & value will be index where this sum is present
- Now start from 1st element & if total_sum_till_here == given-sum, you've got sub-array, print the start & end index
- If total_sum_till_here - given_sum is present in map, it means value exists, so subarray will from start+1 to end
- If total_sum_till_here - given_sum is not present, then you total_sum_till_here as map key

Time Complexity: O(n)
Space Complexity: O(n)

Do Watch video for more info

CHECK OUT CODING SIMPLIFIED

★☆★ VIEW THE BLOG POST: ★☆★

I started my YouTube channel, Coding Simplified, during Dec of 2015.
Since then, I've published over 400+ videos.

★☆★ SUBSCRIBE TO ME ON YOUTUBE: ★☆★

★☆★ Send us mail at: ★☆★

[aestheticboba_yay]

Excellent explanation.. Thank you so much!!

[prashantranjan]

Nice and clear explanation. Please make more video on DP, like maximum sub array, maximum palindrome.. Thank you !!

[AshishGupta-beyz]

good explanation....but in geeks for geeks it doesn't work for some of the test cases

[Prudhvi]

can you tell me for this test case sum=16, arr=[8, 7, 6, 5, 4, 2]

[AnujSharma-egdg]

In problem 1 there is one more subarray[1, 8] of indexes 4 and 5 which is not printed by the code.

[Aestheticslay_yay]

Can you please check the output for this input - - {2, 4, -1, -3, -1, -1, 5, 8} ?

[shahidnx]

Its not o(n) we have sub loops as well. Though we don't iterate sub loops n times but worst case it can be some value 'x'. so complexity is quite higher than (n). It could o(n*x).

[ashwininikam]

Can you give solution of maximum absolute sum of subarray

[apoorvkrishna]

your case for only positive numbers will not work for this case, A=[106, 2, 4] where given sum is 6;