I understand you are trying to solve the questions for everyone. But it feels it has become a chore for you and you are not involved in explaining the crux of the solution and are more concentrated on just spitting out the solution. There is a solution section in leetcode. People come to watch videos because they couldn't understand the solution on a granular level.
Here is the approach : ( you might find it helpful) Say you are given an array e.g. [a0, a1, a2, a3, a4, a5, a6... an] . [a0, a1, a2, a3, a4, a5, a6, ... an] ^ ^ sumI sumJ sumI = sum of numbers till a2 (a0 + a1 + a2) sumJ = sum of numbers till a5 (a0 + a1 + a2 + a3 + a4 + a5) Now lets say the difference between sumJ and sumI is equal to k. What that means is, the sum of numbers between a2 and a5 is equal to k ( a3 + a4 + a5 = k ), which means we found a subarray whose sum is equal to k. We can write a3 + a4 + a5 = k as sumJ - sumI = k and sumJ - sumI = k can be written as sumJ - k = sumI The expression sumJ - k = sumI, means have we already seen a sum which is equal to sum at current index j minus k. If yes, it means we found a subarray whose sum is equal to k. And we keep track of how many times we see a particular sum using a HashMap. Code : class Solution { public int subarraySum(int[] nums, int k) { if(nums == null || nums.length == 0) return 0; int count = 0; Map map = new HashMap(); map.put(0, 1); int sum = 0; for(int i = 0; i < nums.length; i++) { sum += nums[i]; if(map.containsKey(sum - k)) count += map.get(sum-k); map.put(sum, map.getOrDefault(sum,0) + 1); } return count; } }
This is just my suggestion: @2:50 You were finding it hard to explain, i know it's hard to explain it orally. Why don't you use white board and explain your approach first and then start with coding ? That way it would be lot easier to understand the problem as well.
I feel horrible when these walkthrough guys say, "it's not that hard, or it's easy". i'm over an 1 hour in trying to understand the solution and i still don't get it :(, BUT hey, thanks for the video man!! just gotta keep grindinn these leets
We need to realize it requires reverse thinking, the goal is to find how many times/counts that sum of subarrays = k, we put all continuedly sum[i] in the map, for example, when we check 5th position in the map, we find value at (sum[5] - k) = sum[2] in the map(reverse logic), that means nums[2] + nums[3] + nums[3]+ nums[5] = k (normal logic). it means we found 1 count, repeat same process to find final counts.
Given how concise you were, your video was useful for me up to 5 minutes in. After you had explained the idea that the sub-array can contain negative elements, as you were talking about why the hash table should contain key-value pairs of type (Integer, Integer). A little bit of thought on the viewer's end (an informal proof intuition) on what that means, did the job for me. Then the Leetcode solution made sense, a lot like Two Sum, which you also alluded to earlier in the video. The idea for why we need to store the number of occurrences of some number seen in the cumulative sum (rather than just a boolean value): The cumulative sum can only ever equal a number that it's already equaled if there exists a negative sum, followed by a large enough positive sum; furthermore, if this is the case, then we choose any subarray in the region (which we didn't store indices for, unlike Two Sum), s.t. the sum, for any iteration i, is equal to sum_i - k. Since we can choose any of those occurrences, the maximum number of sums, for some iteration i, that equal k would be {hash table}.get(sum_i - k). We simply accumulate this sum in a result variable as we're looping through the array, all in one pass. This problem is a nice extension of the ideas of Two Sum, but the main implementation difference is, instead of storing indices, we store a number of occurrences (understanding why/how is the whole interesting part of this problem and why people stumbled upon this video, in particular, in the first place).
Awesome explanation. At around the three minute mark I almost punched myself thinking "how the heck did I not think of this approach". soo close. Need to keep grinding. Thanks for the video! I do agree with the other viewers that a visual would have been great. Only reason I got this one quick is because I had spent like an hour thinking about it before I came to this vid.
the basic idea is, say sub sum is (i, j) and i < j, then we knew sum(0, j) - sum(0, i) = sum(i, j) which is k. now, sum += num[i], and we wanna know how many sum - k that we have. i.e: ___i__j__ k is between i and j. hope is helps
I can just go to leetcode and see the solution.. dude if you don’t know how to solve the problem, just don’t make a video... it’s funny at the end you said you explained it pretty well but you were literally reading the solution smh
Hey Nick your videos are amazing, and you are doing a great job. However, I feel that you can improve in your videos by explaining on a white board about an algorithm. For instance, step by step explanation and why one should use that algorithm.
Saying "it's clear", "it's pretty obvious" does not really help to explain things, I like your videos overall and you are doing a great job, but I wanted to point that out and hopefully, you can do better.
Really not even sure why you try to put out videos when all you do is to wave hands in air and point out to solutions section of leetcode, which literally anyone can take a look at. This is really becoming a pattern now which, I am guessing, is not very helpful to viewers.
No, because that is the reason we need to count occurrences of a given sum. If a sum S occurs twice and your (current sum - k) == S, this means you will be able to get subarray with sum 'k' in two ways: [right after the first occurrence of S, ..., current index i] and [right after he second occurrence of S, ..., current index i]. Hope it helps because I also did not understand it by his explanation "It's pretty obvious...".
sum - k is the number you need to substract from current sum in order to get a result of k. If you find that sum number in the map it means that sum was calculated earlier to the left of the current point in the array. It's possible you also found that sum number in the map more than once before (hence += ). Does that make sense?
why do you need to keep track of the subarray sum counts in the hashmap?Wouldn't it bee enough to just store the cumulative sums up to(for the) prior indices since you are only concerned with subarrays of size k?
Would not work otherwise. Because at some point you will encounter sum that equals to k and that will equal zero and if you do not add it initially you will never encounter it and it is necessary for solution to be solved. Even if there is zero in initial array adding zero to something does change its value.
Lol "It is pretty easy, just like the twoSum". No it is way harder than the twoSum. Just because you memorized without understanding all the possible scenarios doesn't mean it is "easy".
I understand you are trying to solve the questions for everyone. But it feels it has become a chore for you and you are not involved in explaining the crux of the solution and are more concentrated on just spitting out the solution. There is a solution section in leetcode. People come to watch videos because they couldn't understand the solution on a granular level.
Here is the approach : ( you might find it helpful)
Say you are given an array e.g. [a0, a1, a2, a3, a4, a5, a6... an] .
[a0, a1, a2, a3, a4, a5, a6, ... an]
^ ^
sumI sumJ
sumI = sum of numbers till a2 (a0 + a1 + a2)
sumJ = sum of numbers till a5 (a0 + a1 + a2 + a3 + a4 + a5)
Now lets say the difference between sumJ and sumI is equal to k.
What that means is, the sum of numbers between a2 and a5 is equal to k ( a3 + a4 + a5 = k ), which means we found a subarray whose sum is equal to k.
We can write a3 + a4 + a5 = k as sumJ - sumI = k and sumJ - sumI = k can be written as sumJ - k = sumI
The expression sumJ - k = sumI, means have we already seen a sum which is equal to sum at current index j minus k. If yes, it means we found a subarray whose sum is equal to k.
And we keep track of how many times we see a particular sum using a HashMap.
Code :
class Solution {
public int subarraySum(int[] nums, int k) {
if(nums == null || nums.length == 0)
return 0;
int count = 0;
Map map = new HashMap();
map.put(0, 1);
int sum = 0;
for(int i = 0; i < nums.length; i++) {
sum += nums[i];
if(map.containsKey(sum - k))
count += map.get(sum-k);
map.put(sum, map.getOrDefault(sum,0) + 1);
}
return count;
}
}
Thanks ! This is really clear ! better than anything I have seen on Geeks for Geeks.
@@rrahulm Glad you found it helpful.
nice and clear!!!
Clear explanation. Thanks
Thanks for sharing. Better job in a comment than in 10 min long video.
This is just my suggestion: @2:50 You were finding it hard to explain, i know it's hard to explain it orally. Why don't you use white board and explain your approach first and then start with coding ? That way it would be lot easier to understand the problem as well.
Could you please explain the line 13 .It would be very helpful.
i feel like he's just reading the leetcode discussion
he is lol
I am convinced so many people barely understand the solution that go make a vid about it as quick as possible. It ends up wasting peoples time.
"I think I have explained it pretty well!" No, you didn't.
He's improved; these were his old videos
count=0, b=0;
K=sum to find in subarray
for(i=0;i
I feel horrible when these walkthrough guys say, "it's not that hard, or it's easy". i'm over an 1 hour in trying to understand the solution and i still don't get it :(, BUT hey, thanks for the video man!! just gotta keep grindinn these leets
We need to realize it requires reverse thinking, the goal is to find how many times/counts that sum of subarrays = k, we put all continuedly sum[i] in the map, for example, when we check 5th position in the map, we find value at (sum[5] - k) = sum[2] in the map(reverse logic), that means nums[2] + nums[3] + nums[3]+ nums[5] = k (normal logic). it means we found 1 count, repeat same process to find final counts.
This explaination inspires me, thanks a lot.
@@wilsonwang8641 just had this question for my interview today with TikTok
@@sase1017 Good luck to you buddy, if you pass the interview, just let me know.
Given how concise you were, your video was useful for me up to 5 minutes in. After you had explained the idea that the sub-array can contain negative elements, as you were talking about why the hash table should contain key-value pairs of type (Integer, Integer). A little bit of thought on the viewer's end (an informal proof intuition) on what that means, did the job for me. Then the Leetcode solution made sense, a lot like Two Sum, which you also alluded to earlier in the video.
The idea for why we need to store the number of occurrences of some number seen in the cumulative sum (rather than just a boolean value): The cumulative sum can only ever equal a number that it's already equaled if there exists a negative sum, followed by a large enough positive sum; furthermore, if this is the case, then we choose any subarray in the region (which we didn't store indices for, unlike Two Sum), s.t. the sum, for any iteration i, is equal to sum_i - k. Since we can choose any of those occurrences, the maximum number of sums, for some iteration i, that equal k would be {hash table}.get(sum_i - k). We simply accumulate this sum in a result variable as we're looping through the array, all in one pass. This problem is a nice extension of the ideas of Two Sum, but the main implementation difference is, instead of storing indices, we store a number of occurrences (understanding why/how is the whole interesting part of this problem and why people stumbled upon this video, in particular, in the first place).
stop saying SIZE K when its SUM K
hahaha ok ok ok my bad
@@NickWhite seriously improve that its just so annoying .
oh yes, it annoys a lot.
@@christianoronaldo1662 It is Cristiano, not Christiano. This is definitely not the way to comment
@@shashaankkumarjeebomule7360 aur kuch kam dhanda nhi hai bhai tereko?? meri marzi mai jo rakhu.
Awesome explanation. At around the three minute mark I almost punched myself thinking "how the heck did I not think of this approach". soo close. Need to keep grinding. Thanks for the video! I do agree with the other viewers that a visual would have been great. Only reason I got this one quick is because I had spent like an hour thinking about it before I came to this vid.
the basic idea is, say sub sum is (i, j) and i < j, then we knew sum(0, j) - sum(0, i) = sum(i, j) which is k. now, sum += num[i], and we wanna know how many sum - k that we have. i.e: ___i__j__ k is between i and j. hope is helps
public int subarraySum(int[] nums, int k) {
int count=0;
for(int i=0; i
I can just go to leetcode and see the solution.. dude if you don’t know how to solve the problem, just don’t make a video... it’s funny at the end you said you explained it pretty well but you were literally reading the solution smh
Hey Nick your videos are amazing, and you are doing a great job. However, I feel that you can improve in your videos by explaining on a white board about an algorithm. For instance, step by step explanation and why one should use that algorithm.
Saying it's pretty obvious does not help in understanding the concept :)
Explaining is not typing or fixing compilation errors. Anyone can do it. The solution to this problem lies in line number 13 and you just skipped it.
Saying "it's clear", "it's pretty obvious" does not really help to explain things, I like your videos overall and you are doing a great job, but I wanted to point that out and hopefully, you can do better.
Hey Nick, can you explain subarray with the sum not equal 0.
Really not even sure why you try to put out videos when all you do is to wave hands in air and point out to solutions section of leetcode, which literally anyone can take a look at. This is really becoming a pattern now which, I am guessing, is not very helpful to viewers.
can you help me find the NOT continuous subarray that sums to k? I really can't find a way to it
I can read the problem too.
Will it not have issue of double counting? Because we are doing result += map.get(sum-k)
@Vivek Kapoor I have the same question. Did you find the answer by any chance? @Nick White can you help?
If you could figure it out? 🤔
No, because that is the reason we need to count occurrences of a given sum. If a sum S occurs twice and your (current sum - k) == S, this means you will be able to get subarray with sum 'k' in two ways: [right after the first occurrence of S, ..., current index i] and [right after he second occurrence of S, ..., current index i]. Hope it helps because I also did not understand it by his explanation "It's pretty obvious...".
Can someone please explain those 3 lines?
if (map.containsKey(sum - k))
count += map.get(sum - k);
map.put(sum, map.getOrDefault(sum, 0) + 1);
sum - k is the number you need to substract from current sum in order to get a result of k. If you find that sum number in the map it means that sum was calculated earlier to the left of the current point in the array. It's possible you also found that sum number in the map more than once before (hence += ). Does that make sense?
Leetcode's PathSum III can be solved in the same way
you are doing great job....keep it up. you explain the solution in a very standard way.
Use a board for a better clarity in your explanation
finally the last demo video helped a lot
that is a demo on Leetcode not his
"THAT'S THE WHOLE THING!"
Not a very clear explanation. I concur with the general sentiments in the comments section.
why do you need to keep track of the subarray sum counts in the hashmap?Wouldn't it bee enough to just store the cumulative sums up to(for the) prior indices since you are only concerned with subarrays of size k?
hakan topaloglu same question
If you could figure it out, why is it so?
Can you do another video explaining the same problem please? Would be helpful.
"Array of size k" why?? Shouldn't it be an array with "sum = k".
I tried using the Sliding Window method for this, but it won't work :(
because of negative numbers, sliding window wont work
got this question in one of the interviews, was not able to come up with solution :/
Can someone explain why we line 5 in the code..
Would not work otherwise.
Because at some point you will encounter sum that equals to k and that will equal zero and if you do not add it initially you will never encounter it and it is necessary
for solution to be solved.
Even if there is zero in initial array adding zero to something does change its value.
Thank you NIck for this video you really helped me understand it
7:48 how can sum of that subarray be zero?
If some of the elements are positive and some negative,values might cancel each other
Why mp(0)=1
is it solvable using a sliding window approach?
yhd d Yes
@@joegerges99 No it contains negative numbers..so it cant be
This is what we want from you
Hi Krishna did u understand what he thought . If u don't mind text me in WhatsApp +917358252858 so that I would clarify my doubts from u . Thx
use a whiteboard :)
For the testcase [-1, -1, 1] it may not work if the k=0
Can someone explain me for this ?
it works
@@jasonchen8566 Hey thanks buddy for reply
Highly appreciated
thanks it helped me solve my doubt
thanks
thanks,
thanks.. helped a lot :)
Finally I got a channel for my preparation
i have problem with writing algorithm for BODMAS rule . Can you please make a video(JAVA) explaining the solution
please post dp problems!
Hey your concepts are very clear.
How many Indian viewers do you have lol
Thank you for the easy explanation
Lol "It is pretty easy, just like the twoSum". No it is way harder than the twoSum. Just because you memorized without understanding all the possible scenarios doesn't mean it is "easy".
you're a legend
You are very good at programming, however, you cannot explain it very well. May be because you dont use whiteboard to explain it.
Great video. Thanks !
I accidentally fell in love with you
i clicked on the video just to dislike