Subarray sum equals K | Number of subarrays with sum equals K | Leetcode #560

This video explains a very important programming interview problem which is to count the number of subarrays in a given array with sum exactly equals to K. This is leetcode #560 coding problem. I have shown the solution using many approaches. I have started with bruteforce approach and went on to finally show the most optimal approach for this problem. I have taken examples to arrive at the optimal approach from the most intuitive approach. Finally, i have shown the CODE for the optimal approach and the CODE LINK is given below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

[therealvortex]

If anyone is confused why the count was increased by myMap[ curr - k ] instead of just count+=1 . It was because prefix sum can be same because of some negative values in the array. so out next occuring k will also pair with those negative values also .


consider this case A : [3 4 7 2 -3 1 4 2 1 ]
preSum : [3 7 14 16 13 14 18 20 21]


you can see 14 occured twice because of the subsequence [2 -3 1] their sum is 0. so When you are at the final index with value 1 . you have curr - k = 21 - 7 = 14 . you check for 14 it has occured twice . so you need to consider subsequences [2 -3 1 4 2 1] and [4 2 1] . Hope this helps

[seyidaniels]

I wish youtube has a clap feature! this explanation deserves a million claps

[jamesmacharia]

Watched like a billion videos and it's only this visual representation that made sense. Thanks, Man!

[hemantv]

count=0, b=0;
K=sum to find in subarray
for(i=0;i<n;i++)
{
for(j=i;j<n;j++)
{
b+=a[j];
if(b==k)
count++;
}
b=0;
}
printf("%d", count);

This might work for above problem with O(n^2) complexity

[rongav]

Loved your approach man you didnt go straight to the code. You explained brute force and then optimized it like a coding interview. Thanks for this explanation!

[anandkrishnan]

If anyone does not understand why we look for sum - k within our map, this is why: as we are calculating our prefix sum for all of the elements that we have traversed so far, if we see that in some point in our previous prefix sums, we have found our current prefix sum - k, then that means between our current prefix sum and the one that we have found using our hashmap, we have traversed an array of sum K. Essentially, at each point in our prefix sum, we are looking to see if we can add K to get to our current prefix sum as this tell us that we have seen a subarray of sum k. This was really hard for me to understand for some reason. Hopefully this helps someone.

[kirtikedia]

Loved the overall explanation
Since we want count of k=7, we can make use of unordered_set whose time complexity is again O(1). For that case we dont need to keep count of each and every sum and increment count only when sum = 7 which will be our final result.

[안광훈-xp]

Your visualization with an example going through is very intuitive & easy to understand, thanks for helping me understand :)

[denniskang]

Again, I watched many other videos and still not clear. Your video is by far the best, so clear and explain without any confusion. Thanks! Great job!

This explanation is much better than a lot of others I found in YouTube and leer code.

[jasonng]

This is the most comprehensive explanation I've found on Youtube...
But I don't really understand why this is a Computer Science problem. it feels like this is a Mathematics philosophy...

[chetanpatteparapu]

Why can't we use Set<Integer> when we are only looking for values which are present in the HashMap;

[vman]

Key observation is from 10:52 - 11:22. This clarified a lot for me.

One question I still had was: why do we need to use a HashMap which stores the counts if the counts never get used? Couldn't we just use a HashSet? Well, a comment by Guilherme GM shows that if you have more than one subarray in your array with sum equal to currSum-K, you need to increment the counter by the number of subarrays (not by 1) since the index after the end of any of them could be the start of a new subarray whose sum equals K.

Otherwise, great explanation -- best one of this problem on YouTube.

[daksh]

If the array was with all positive integers then could we use the sliding window method to solve it ?

[_just_for_fun_]

bro you killed it man...just one shot of your video is enough to understand the whole logic....thank you so much....

[danielmcgee]

could you explain why we are adding myMap[sum-k] instead of just incrementing count? i dont see why you need to add the count of how many times you have the item in the map instead of just incrementing?

[DearDextra]

I watched nick white's video prior to this video, his explanation wasn't quite good enough. Thank you for drawing it out and doing an iteration to show how hashmap method works. My guy nick was like, oh so this problem is simple, here use a hashmap, there, its done.

[shruthey]

I have been looking for a video that clearly explains the reason to check for "sum-k" exists in the subarray? and this is the only video that clearly got into the detailed explanation. Thank you for not saying "It's easy to understand" without actually saying anything 😅

[VaishnaviNigam]

Sir just 1 line m struggling with.... is when I tried to do it, i did the same approch but with SET, and my answer is not coming correct.Moreover why wasnt count++ but instead u did count+=map[currsum-k]
I m not Getting this Line's Logic... would u plz take a minute n explain me

[MrGamer]

We could also remove the if(currSum==k) condition and initialize the map with map[0]=1. So that the (sum-k) (7-7) if k =7 will be 0 and its count value will be already there in the map. Now the second if loop will increment the count value.