If you are having difficulty understanding this or wrapping your head around the solution, maybe this might be a good way to think about it. The question asks how many subarray sum equals to k. For a subarray to sum to k, you need a subarray, as in a part of the array from index 'a' to index 'b' to have a sum equal to k. But when we reach any index 'b', we obviously do not know, if there was a subarray from index 'a' to index 'b' equal to k. However we do have the sums from 0 to index 'a' in our hash map, because we have been storing all sums starting from index '0' to every single index till now, and the count of them as the value of the key. Now obviously sum_0_to_a + sum_a_to_b = total sum so far (curSum). If we go to the original ask, which is we need a prefix that is sum_a_to_b to be equal to k. For that to hold true, replace sum_a_to_b with 'k'. Hence, sum_0_to_a + k = curSum. Hence curSum - k = sum_0_to_a. And then since we have been storing all possible values of sum_0_to_a so far in the hashmap, curSum - k must exist in the hashmap as a key, and we can simply add the value from the hashmap to add number of prefixes from 0 to any index which equalled to curSum - k .
You know I remember first learning CompSci, I thought the specific algorithm concepts (BFS, DFS, Dijkstra, etc.) were the hard ones to learn. Now that I am more experiences, I realize that the what I thought then were 'basic' data structures, i.e. arrays, strings, etc. are actually the harder ones to make sure you understand because those concepts has many dedicated algorithms to them, such as Kadane, prefix/suffix array, KMP etc. that you need to know to truly understand that data structure. So while I glossed over arrays because I knew their functions, I am now revisiting to make sure I understand the algorithms embedded in them. Learning truly never does stop!
Honestly same here. I figured that arrays would be relatively simple, and they are simple on the surface, but there are so many algorithms and different types of problems that involve them that it feels like they're an entire rabbit hole unto themselves.
Thanks, NeetCode for these solutions and explanations, It would be really helpful to make a video about general techniques that you use to solve these problems... Because we wan to know how to approcah these kinds of problems by ourselves. Thanks again.
We cannot. These are classic problems asked during interviews. Whoever come across this problem would easily solve it. Other would go with bruteforce approach which doesn't work on interviews.
@@darshana5254 thanks bro, you’ve raised a very important point. Only if one has encountered such problems, only then will he be able to solve the problem cuz he knows how to optimum approach.
I got this question in the interview and I did not know the optimal solution. However I was able to produce the n^2 solution quickly and the interviewer started giving me hints to use Hashmap to reduce it to O(N). I scrambled here and there but was able to talk about the "repeated work" being done and how I could use hashmap to save the work. In the end I was not able to code it up. Interviewer still passed me though.
Good explanation and, fortunately, the omission of the [key = 2, count = 1] map entry did not affect the result. However, it would be good if NeetCode could add text at that part in the video to make it clear what happened.
08:21 - i have no idea how we are supposed to figure out during the coding interview that (0,1) has to be added into the hashmap by default. How is anyone solving this without memorizing during interviews? May be i'm dumb to not understand this even though the instructor is explaining it. Please help me understand the intution behind adding (0,1) in hashmap by default.
I thought about it as a sliding window problem until I found out there can be negative values. If we would only have positive ones, you would increment right pointer while sum is less than k, then increment left while sume is more than k. That would be my approach (not tested).
@@ziomalZparafii the main problem behind sliding window approach is some edge cases. For example: [1,-1,0], k = 0 If we will use two pointers approach (or dynamic sliding window), then we will return 2 instead of 3. 1) sum=1, count=0, left=0, right=0 2) sum=0, count=1, left=1, right=1 3) sum=0, count=2, left=2, right=2
@@ziomalZparafii you still can use a sliding window with negative numbers, it depends on requirements and edge cases, so your first comment is not entirely accurate.
Yeah it's complicated but don't forget to come up with the optimal solution in 10 minutes without any compiler errors and of course it needs to pass all test cases in the interview. smh. Tech interviewing has become a circus.
i appreciated you explaining this. But, it would have been more helpful(esp to people like me) where you would have taken the time to explain more about the use of HashMap for maintaining prefixSum -> Count to me it felt like the explanation went "too fast" as soon as you discussed the brute force solution.But, in any case a great attempt indeed.
A slightly cleaner solution using a defaultdict class Solution: def subarraySum(self, nums: List[int], k: int) -> int: prefixSums = defaultdict(int, { 0 : 1 }) curSum = 0 res = 0 for n in nums: curSum += n res += prefixSums[curSum - k] prefixSums[curSum] += 1 return res
It's a good combination of two sum and prefix sum. And the intuition should be: 1. subarray sum -> prefix 2. equals k -> two sum The only difference is it's 'b - a = k' instead of 'b + a = k', and you just need to calculate the 'a' differently.
so what you are saying is we have a map that shows how many ways we can come up with given sum so for sum 0 we can come up with 2 sequences, but these sequences have to be contiguous , how to prove that 0 has 2 only if we pop up contiguous elements from current sum ?
How are you supposed to figure this out in 30 minutes? I watched this three times and didn't look at the code at the end, I was able to figure it out and code it quickly once understanding what you're supposed to do, but I couldn't figure it out at all during an interview once I realized there could be negative numbers. Why would having negative numbers not just twist the problem up a bit, but ENTIRELY change the approach and fundamental way to solve it? Ridiculous.
I don't understand why you kept Prefix Sum of 0 and count 1 when you started over and changed the index 1 element from 1 to -1. It's a new example, why did you not reset the hash table?
Do you know what's the drawback of your videos are? You take plenty of time just to explain why 2+2 = 4, I mean just explaining the basics of the logic to think of and same logic in many examples, repeating the same line to expand the length of video. While explaining how to write that logic in any computer language you are using, BOOM, in just a few seconds. I think maximum of the viewers search the explanation to understand how to write or explain the software to do that, not just the logic. Please think of that.
Another way to think about why we would set our key value to {0:1} instead of memorizing, is to think what if that single element, itself is the target. For example: input = [1, 1, 4] , k = 4 occur = { 0: 1 } By just eyeballing, you'll see the output is 1, since the last element is a 4. When we iterate through the input, we'll do input[2] - k (4 - 4) = 0. Do we have a 0 in our hashmap/dictionary? Yes we do, it's value is 1.
except in this scenario wouldn't we be doing currSum - k (6 - 2) = 2, and we would be looking up the value for 2 in our hash map, which would be 1. I think your scenario only works if the single element that is the target is the first element in the input.
Why doesn't sliding window approach fails here: - Assumption: adding an element to increase and removing an element to decrease any sum is valid only if all elements are non-negative. - removing negative elements increases total sum and vice versa, hence breaks tests containing negative number - not suitable approach for this problem
Is it just me that did not get anything? Prefix sum is very hard to understand even if we see the solution. Coming to a solution for entire new question in an interview is very difficult.
Hi @NeetCode. I am not able to understand the part where you say. we need to add the prefix sum to Hashmap simultaneously. even if are maintaining the Hashmap first. we can still get count of prefix - k and prefix = k.
Take this example: [1]; k = 0. Without adding first your prefix sum array would be: 0->1 and 1->1. Now you will compute prefixSum-k for each key. 0 - 0 = 0, You say you have a match(which is just the empty prefix). Now you compute 1- 0 = 1, you check your map and the value exists, so you return a count of 2. That is why the update needs to happen simultaneously. So, that you can check the subarray between some starting index "i" and current index "k"(excluding k). Hope this makes sense.
I see some confusion on why we initialize prefixSum = {0:1}, and that's because we can always produce 0 by taking no elements from our array (e.g. []). This works out nicely when we run into a subarray that has a sum == k, because sum - k = 0. Then the question we ask at this moment is "is there a prefix-subarray I can take away from my current subarray sum that also equals 0?" The answer is yes, because I can takeaway no elements from my current subarray and the current subarray sum will still equal k.
I have a doubt. If the array is 6,4,3 and k is 9. we find that sum till n is 13 and 13-k ie 13-9=4 is present in the array so that will get counted but in reality it is wrong as it is not a subarray is we dont pick contiguous element. please explain
I understood this explanation! Thanks!! I was trying with sliding window technique first and getting the wrong answer until I realised that we can have negative numbers. This is indeed is a neat.
I am not sure, but take an example where the array is [-1,1,-1] and k>0(e.g., 2). The result would be 1, since after the 1 is covered, and then we went into the -1 again, the result will be 1, and that's not true (should be 0). Am I missing something? I think the results should be added only if the cursum is >=k
Did this problem but used an array to keep track of the running totals then reversed it... used a deque after but wow is deque slow and memory intensive
u forgot to add 2,1 to the hashmap
Good catch, i was thinking about that too bc its easier to see the pattern if its consistent on when u add (even if its not needed for this example)
I just spent like 10 minutes rewinding and forwarding the video trying to understand why 2 wasn't added. Thankfully, I found your comment now.
Actually, it is just not {2:1}. He forgot to add the current sum to the hash table when it is not found in the table.
Yup .. I was also thinking about that ..
haha yeep. my OCD went brrrr... I was like wheres the 2 :P ..
If you are having difficulty understanding this or wrapping your head around the solution, maybe this might be a good way to think about it. The question asks how many subarray sum equals to k. For a subarray to sum to k, you need a subarray, as in a part of the array from index 'a' to index 'b' to have a sum equal to k. But when we reach any index 'b', we obviously do not know, if there was a subarray from index 'a' to index 'b' equal to k. However we do have the sums from 0 to index 'a' in our hash map, because we have been storing all sums starting from index '0' to every single index till now, and the count of them as the value of the key. Now obviously sum_0_to_a + sum_a_to_b = total sum so far (curSum). If we go to the original ask, which is we need a prefix that is sum_a_to_b to be equal to k. For that to hold true, replace sum_a_to_b with 'k'. Hence, sum_0_to_a + k = curSum. Hence curSum - k = sum_0_to_a. And then since we have been storing all possible values of sum_0_to_a so far in the hashmap, curSum - k must exist in the hashmap as a key, and we can simply add the value from the hashmap to add number of prefixes from 0 to any index which equalled to curSum - k .
I like your attempt to explain it, even though I don't fully understand it. I appreciate it.
U should
lmao
You know I remember first learning CompSci, I thought the specific algorithm concepts (BFS, DFS, Dijkstra, etc.) were the hard ones to learn. Now that I am more experiences, I realize that the what I thought then were 'basic' data structures, i.e. arrays, strings, etc. are actually the harder ones to make sure you understand because those concepts has many dedicated algorithms to them, such as Kadane, prefix/suffix array, KMP etc. that you need to know to truly understand that data structure. So while I glossed over arrays because I knew their functions, I am now revisiting to make sure I understand the algorithms embedded in them. Learning truly never does stop!
Honestly same here. I figured that arrays would be relatively simple, and they are simple on the surface, but there are so many algorithms and different types of problems that involve them that it feels like they're an entire rabbit hole unto themselves.
Facts man
factssss, at a point i thought smth is wrong with the way i think .
Thanks, NeetCode for these solutions and explanations, It would be really helpful to make a video about general techniques that you use to solve these problems... Because we wan to know how to approcah these kinds of problems by ourselves. Thanks again.
I'm still trying to wrap my head around this
EDIT: Came back a few weeks later and it makes 100% sense to me now
Me right here
i think im just dumb af bc i still dont understand it
Great explanation.
How are we supposed to come up with a solution like this in 30m without having seen it before!
We cannot. These are classic problems asked during interviews. Whoever come across this problem would easily solve it. Other would go with bruteforce approach which doesn't work on interviews.
@@darshana5254 thanks bro, you’ve raised a very important point. Only if one has encountered such problems, only then will he be able to solve the problem cuz he knows how to optimum approach.
That's the neat part. You don't.
I got this question in the interview and I did not know the optimal solution. However I was able to produce the n^2 solution quickly and the interviewer started giving me hints to use Hashmap to reduce it to O(N). I scrambled here and there but was able to talk about the "repeated work" being done and how I could use hashmap to save the work. In the end I was not able to code it up. Interviewer still passed me though.
@@vineethsai1575 what company
Good explanation and, fortunately, the omission of the [key = 2, count = 1] map entry did not affect the result. However, it would be good if NeetCode could add text at that part in the video to make it clear what happened.
It's not about a bug in the code, it's about a bug in the video. 9:55 Here you should have added key 2 and value 1 to the hashmap and that's it.
08:21 - i have no idea how we are supposed to figure out during the coding interview that (0,1) has to be added into the hashmap by default. How is anyone solving this without memorizing during interviews? May be i'm dumb to not understand this even though the instructor is explaining it. Please help me understand the intution behind adding (0,1) in hashmap by default.
bcs if you find that n-k = 0 means that you dont need to remove anything so basically it be 0, 1 by default
1:55 I needed to hear that, I wanted to know why sliding window won't guarantee correct answer for these constraints. That cleared it up.
Initially I thought it was a sliding window problem, Trying to wrap my head around this ...patience, time...ahhh. Thanks for the video!
I thought about it as a sliding window problem until I found out there can be negative values. If we would only have positive ones, you would increment right pointer while sum is less than k, then increment left while sume is more than k. That would be my approach (not tested).
@@ziomalZparafii the main problem behind sliding window approach is some edge cases. For example: [1,-1,0], k = 0
If we will use two pointers approach (or dynamic sliding window), then we will return 2 instead of 3.
1) sum=1, count=0, left=0, right=0
2) sum=0, count=1, left=1, right=1
3) sum=0, count=2, left=2, right=2
@@aleksandr_t you have a negative value in your array. Read my comment once again :-)
in a real interview we can not make this mistake, it will take you 20 mins to find out sliding window will not work
@@ziomalZparafii you still can use a sliding window with negative numbers, it depends on requirements and edge cases, so your first comment is not entirely accurate.
Well explained, and it takes effort to make a video as good as this. Thank you!
00:40 The brute force approach is O(n^3), not O(n^2). There are ~n^2 subarrays but summing a subarray is O(n).
the idea that we're expected to come up with this solution on the fly in an interview is bonkers to me
Just failed this one in an interview. I just don't get it even when with such detailed explanation
Yeah it's complicated but don't forget to come up with the optimal solution in 10 minutes without any compiler errors and of course it needs to pass all test cases in the interview. smh. Tech interviewing has become a circus.
i appreciated you explaining this. But, it would have been more helpful(esp to people like me) where you would have taken the time to explain more about the use of HashMap for maintaining prefixSum -> Count to me it felt like the explanation went "too fast" as soon as you discussed the brute force solution.But, in any case a great attempt indeed.
This is a LC hard imo, gawd damn!
Agree, it's definitely more difficult than some actual hard problems.
Why did you initialised your dictionary before hand with (0:1)
Wayyyy less confusing than the explanation on leetcode
Why are array and string problems 10x harder than graph, matrix and dp???
yeah atleast graph matrix dp follow a single type of questions these are like so different from each other
A slightly cleaner solution using a defaultdict
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
prefixSums = defaultdict(int, { 0 : 1 })
curSum = 0
res = 0
for n in nums:
curSum += n
res += prefixSums[curSum - k]
prefixSums[curSum] += 1
return res
Crazy good explanation. Subscribed. Thank you man !
It's a good combination of two sum and prefix sum.
And the intuition should be:
1. subarray sum -> prefix
2. equals k -> two sum
The only difference is it's 'b - a = k' instead of 'b + a = k', and you just need to calculate the 'a' differently.
i still dont get it, im dumb
This is a way better explanation than leetcode premium’s explanation thank you!
You explained it so perfectly that I didn't even need to see the code to be able to code it myself :) thank you!!
so what you are saying is we have a map that shows how many ways we can come up with given sum so for sum 0 we can come up with 2 sequences, but these sequences have to be contiguous , how to prove that 0 has 2 only if we pop up contiguous elements from current sum ?
just gotta keep practicing! Thank you Neetcode for making all these amazing videos!
How are you supposed to figure this out in 30 minutes? I watched this three times and didn't look at the code at the end, I was able to figure it out and code it quickly once understanding what you're supposed to do, but I couldn't figure it out at all during an interview once I realized there could be negative numbers. Why would having negative numbers not just twist the problem up a bit, but ENTIRELY change the approach and fundamental way to solve it? Ridiculous.
I don't understand why you kept Prefix Sum of 0 and count 1 when you started over and changed the index 1 element from 1 to -1. It's a new example, why did you not reset the hash table?
Do you know what's the drawback of your videos are? You take plenty of time just to explain why 2+2 = 4, I mean just explaining the basics of the logic to think of and same logic in many examples, repeating the same line to expand the length of video. While explaining how to write that logic in any computer language you are using, BOOM, in just a few seconds. I think maximum of the viewers search the explanation to understand how to write or explain the software to do that, not just the logic. Please think of that.
Another way to think about why we would set our key value to {0:1} instead of memorizing, is to think what if that single element, itself is the target.
For example:
input = [1, 1, 4] , k = 4
occur = { 0: 1 }
By just eyeballing, you'll see the output is 1, since the last element is a 4. When we iterate through the input, we'll do input[2] - k (4 - 4) = 0. Do we have a 0 in our hashmap/dictionary? Yes we do, it's value is 1.
except in this scenario wouldn't we be doing currSum - k (6 - 2) = 2, and we would be looking up the value for 2 in our hash map, which would be 1. I think your scenario only works if the single element that is the target is the first element in the input.
just wow!!
Why doesn't sliding window approach fails here:
- Assumption: adding an element to increase and removing an element to decrease any sum is valid only if all elements are non-negative.
- removing negative elements increases total sum and vice versa, hence breaks tests containing negative number
- not suitable approach for this problem
No way anyone can come up with this in an interview
get() is unnecessary can just add to hashmap regularly. this drawing analysis is goated though!!!
too many unnecessary words, people who practice this is smart enough to understand with just a 1 minute video recap
10:02 Why didn't we add 2 as a prefix there? Was that a mistake on your part? I'm confused.
Yep, should have been added
I think using Kadane’s algorithm it should be simple
How does this solution prevent subarrays that sum up to k from being counted more than once? I don't get it.
what a great explanation , saw many videos, amazing explanation of intuition.
Whats wrong with this recursion code ??
int solve(vector& nums, int k, int n, int curr) {
if(n==0) return 0;
int res=0;
curr+=nums[n-1];
if(curr==k) {
res++;
} else {
res+=solve(nums, k, n-1, curr);
}
res+=solve(nums, k, n-1, 0);
return res;
}
int subarraySum(vector& nums, int k) {
int n=nums.size();
return solve(nums, k, n, curr);
}
Is it just me that did not get anything? Prefix sum is very hard to understand even if we see the solution. Coming to a solution for entire new question in an interview is very difficult.
Absolutely love this guy, not lessons but a masterpiece!
Still dont get how to arrive at using a map, no intuition
This is a crappy problem
damn this question is much harder than i thought
thank you for the explanation tho
What a god of prefix sums. Great vid!
I feel bad for watching solutions, but I don't know what else to do
Can it be considered as a dynamic programming solution?
By far the best explanation to this problem
you say "right" waaaaay too much; it's pretty distracting
I'm even more confused than I was before I saw this video.
Just wonder why the prefix sum 2 is not in the hashmap.
Hi @NeetCode. I am not able to understand the part where you say. we need to add the prefix sum to Hashmap simultaneously. even if are maintaining the Hashmap first. we can still get count of prefix - k and prefix = k.
Take this example: [1]; k = 0. Without adding first your prefix sum array would be: 0->1 and 1->1. Now you will compute prefixSum-k for each key. 0 - 0 = 0, You say you have a match(which is just the empty prefix). Now you compute 1- 0 = 1, you check your map and the value exists, so you return a count of 2. That is why the update needs to happen simultaneously. So, that you can check the subarray between some starting index "i" and current index "k"(excluding k). Hope this makes sense.
I don't understand why line 12 is necessary
It's easier to use defaultdict instead of the .get
but how do you know the difference will be contigous with the current sum ?
Because you substract a prefix, you don't select element in your window
Your channel is really underrated man 😢
Truth.
This reminds me of the two sum solution.
I wrote a dp and find out that same as brute force ...
Bless you, O savior from heavens above!!
Godlike explanation to a looked easy problem. Hats off my man
this is the first neetcode, i didn''t understand XD
this question not in you 150 problem set?
Not clear bro. Delete my comment now
No way I can get the solution in interview
im so dumb, never gonna get this.
This is a valuable problem.
I see some confusion on why we initialize prefixSum = {0:1}, and that's because we can always produce 0 by taking no elements from our array (e.g. []). This works out nicely when we run into a subarray that has a sum == k, because sum - k = 0. Then the question we ask at this moment is "is there a prefix-subarray I can take away from my current subarray sum that also equals 0?" The answer is yes, because I can takeaway no elements from my current subarray and the current subarray sum will still equal k.
is this question on neetcode? i cant locate it
Awesome explanation❤️
Can you plz solve
Count submatrices with all ones?
This is by far the best explanation in the web for this problem, thank you so much NeetCode!
amazing explanation :)
I was actually asked this question for a Facebook internship position in 2019.
Did you find the optimal solution in an interview? Had you seen this problem before? If no, did you pass that round?
What is the name of this algorithm?
There is another edge case for adding 0->1in the starting , which is if the. nums[0] is 0. This intuition is quite tricky but great explanation.
I have a doubt. If the array is 6,4,3 and k is 9. we find that sum till n is 13 and 13-k ie 13-9=4 is present in the array so that will get counted but in reality it is wrong as it is not a subarray is we dont pick contiguous element. please explain
great solution thank you
Really good explanation. Thanks.
I understood this explanation! Thanks!! I was trying with sliding window technique first and getting the wrong answer until I realised that we can have negative numbers. This is indeed is a neat.
Never been more lost in my life
This guy is Goated 🚀
this should be a hard T.T
I don't know why it works, but still works! ;)
Everytime I have to revisit the solution before interview. ;(
Do the next harder version of this which is Continuous Subarray Sum 523
I am not sure, but take an example where the array is [-1,1,-1] and k>0(e.g., 2). The result would be 1, since after the 1 is covered, and then we went into the -1 again, the result will be 1, and that's not true (should be 0). Am I missing something?
I think the results should be added only if the cursum is >=k
amazing explanation!!
Oh man its a brain gym ...
I have watched at least 50 of your videos and this is the only one I found difficult to understand. Nevertheless, thank you for your content.
Delete my new comment
Bawal item ho Yaar. 👌Hats off 🫡
not clear explanation
Did this problem but used an array to keep track of the running totals then reversed it... used a deque after but wow is deque slow and memory intensive
Mind = blown.
nice explaination
thank you man!!
How feasible would it be to solve this kind of problem at the interview, given you never seen the solution before?
Very informative man. Keep up the good work.