Thanks for the kind words! I can't remember which video it was where I completely butchered the explanation for this class of question but I guess it wasn't this one. Definitely a hard topic to explain even though in my head it all makes sense
Using a defaultdict(int) makes the check if the key is in the dictionary unnecessary (line 15), as the defaultdict automatically initializes the value to 0 if the key does not exist.
Here's an explanation that made sense to me : we use the existing array values and prefix sums to compute the sub array values (which is linear time) on the fly instead of computing all of them (which is quadratic time). It's kind of like two-sum once you get this intuition
At first glance, I couldn't catch up but If we observe carefully it is similar to the two-sum problem and we need to know which point we just need to see if any of the pre-calculated prefixes match with current_sum - k Thanks for your explanation It helped a lot.
I think if sum(i) - sum(j) = 0 that means sum(i+1 to j) including element at j equals 0, right? In the example prefix sum of [1,2,3,-3] is [1,3,6,3] so sum(0..1)-sum(0..3) = 0 so sum(2..3) = 0 i=1, j=3 sum(i+1..j)
You do not need this strange init. It is hard to grasp. Just add this as the second operation in the loop instead `res += int(prefix_sum == k)` also this if statement could be replaced by `res += prefix_dict.get(prefix_sumn-k, 0)`
haha, I did this question sooo many times trying to understand prefix sum questions. I was able to code it up from memory, but was totally shook if I got asked it in an interview.. because explaining my thought process :D Seriously this question is hard af. Screw the medium rating.
Yea it's just one of those where you really need a pen and paper to hammer in the logic. Once it clicks you can understand the solution to all these types of questions but I agree it's really hard the first time seeing it.
prefix sum says that each next number in prefix sum array should be the sum of the previous ones and the number itself. So, if prefixes = [1, 3, 9, 4], nums = [1, 2, 6, -5] if nums = [1, 2, 7, -3], prefixes = [1, 3, 10, 7] ( 1, 1+2, 1+2+7, 1+2+7-3)
Tell me one thing, how can someone solve this question in 20-25 min with optimal solution if they have not seen it before. Sorry but I was frustrated to understand this. Also this is from Chatgpt for more understanding. If we have a prefix sum up to index j (let's call it sum_j), and we've seen a prefix sum (sum_i) such that sum_j - sum_i = k, then the subarray between i+1 and j (inclusive) has a sum of k. Here's why: sum_i represents the sum of all elements from index 0 to i. sum_j represents the sum of all elements from index 0 to j. The difference (sum_j - sum_i) represents the sum of elements from index i+1 to j. Let's break it down: sum_i = nums[0] + nums[1] + ... + nums[i] sum_j = nums[0] + nums[1] + ... + nums[i] + nums[i+1] + ... + nums[j] sum_j - sum_i = (nums[0] + nums[1] + ... + nums[i] + nums[i+1] + ... + nums[j]) - (nums[0] + nums[1] + ... + nums[i]) sum_j - sum_i = nums[i+1] + ... + nums[j] So, when sum_j - sum_i = k, it means the sum of elements from index i+1 to j is equal to k. This is why in the implementation, we don't need to make any adjustments when we find a match. The current index represents the end of the subarray (j), and the hashmap gives us the count of prefix sums that, when subtracted from the current sum, yield k. Each of these represents a valid subarray ending at the current index.
Unfortunately you really are expected to have seen the question before and memorised the solution. That or you've solved so many similar problems you can use prior experience to solve it. The system is broken, but at least for Meta you know the list of questions ahead of time (the LC list) so you can just practice practice practice the most frequently asked ones.
Thanks for making the videos. Yes I am trying to finish top 75 last 6 months meta questions and see if I can pass phone screening . Never did leet code . But it's the truth , we need to play this game of dsa and algos. Again thanks for making these videos .
@@crackfaang I have 32 years of experience and I was a manager at google. We hired a front end engineer that passed the interview with glory...few weeks later I realized this person did not know anything about front end. I asked to see the loop question.... all leetcode questions... I feel it is like pockets in pijamas ... almost but not totally, useless
Yea this is the shit explanation. My better one for the divisible/equals K problems is in the video for Subarray Sums Divisible By K. It's one of those where if you know how it works it all makes sense but explaining it is harder than learning it lol
[1,1,1] .. i can have element 0 and 1 =2, element 1 and 2 = 2 as you said.. but I also can add the element 0 and 2 and have 2... so 3 sub-arrays not 2. The description of this exercise sucks
"prefix_dict[0] = 1" basically replaces "if prefix_sum == k: counter += 1" in our loop
Probably the best explanation on the whole TH-cam, thank you man!
Thanks for the kind words! I can't remember which video it was where I completely butchered the explanation for this class of question but I guess it wasn't this one. Definitely a hard topic to explain even though in my head it all makes sense
Using a defaultdict(int) makes the check if the key is in the dictionary unnecessary (line 15), as the defaultdict automatically initializes the value to 0 if the key does not exist.
Here's an explanation that made sense to me : we use the existing array values and prefix sums to compute the sub array values (which is linear time) on the fly instead of computing all of them (which is quadratic time). It's kind of like two-sum once you get this intuition
What a horrible question! Thanks so much for all you do , you are appreciated !
It's nice to know that I'm not the only who has a hard time explaining this one, lol.
Welcome as a channel member mate!
At first glance, I couldn't catch up but If we observe carefully it is similar to the two-sum problem and we need to know which point we just need to see if any of the pre-calculated prefixes match with current_sum - k
Thanks for your explanation It helped a lot.
I think if sum(i) - sum(j) = 0 that means sum(i+1 to j) including element at j equals 0, right? In the example prefix sum of [1,2,3,-3] is [1,3,6,3] so sum(0..1)-sum(0..3) = 0 so sum(2..3) = 0 i=1, j=3 sum(i+1..j)
sumI - k = sumJ, where I < J, was the key
You do not need this strange init. It is hard to grasp. Just add this as the second operation in the loop instead
`res += int(prefix_sum == k)`
also this if statement could be replaced by
`res += prefix_dict.get(prefix_sumn-k, 0)`
haha, I did this question sooo many times trying to understand prefix sum questions.
I was able to code it up from memory, but was totally shook if I got asked it in an interview.. because explaining my thought process :D
Seriously this question is hard af. Screw the medium rating.
Yea it's just one of those where you really need a pen and paper to hammer in the logic. Once it clicks you can understand the solution to all these types of questions but I agree it's really hard the first time seeing it.
thanks for the awesome explanation!
had a question, in the example, shouldn't it be prefixes = [1, 3, 9, 4], if nums = [1, 2, 7, -3]?
prefix sum says that each next number in prefix sum array should be the sum of the previous ones and the number itself.
So, if prefixes = [1, 3, 9, 4], nums = [1, 2, 6, -5]
if nums = [1, 2, 7, -3], prefixes = [1, 3, 10, 7] ( 1, 1+2, 1+2+7, 1+2+7-3)
Ah wow!!! Never knew about this feature, nice to know :)
You've been along for so long you've more than earned the right to just request the content you want to see. Just DM me on discord
why not just res += 1?
Emotional Damage @ 5m 31s
Tell me one thing, how can someone solve this question in 20-25 min with optimal solution if they have not seen it before. Sorry but I was frustrated to understand this.
Also this is from Chatgpt for more understanding. If we have a prefix sum up to index j (let's call it sum_j), and we've seen a prefix sum (sum_i) such that sum_j - sum_i = k, then the subarray between i+1 and j (inclusive) has a sum of k.
Here's why:
sum_i represents the sum of all elements from index 0 to i.
sum_j represents the sum of all elements from index 0 to j.
The difference (sum_j - sum_i) represents the sum of elements from index i+1 to j.
Let's break it down:
sum_i = nums[0] + nums[1] + ... + nums[i]
sum_j = nums[0] + nums[1] + ... + nums[i] + nums[i+1] + ... + nums[j]
sum_j - sum_i = (nums[0] + nums[1] + ... + nums[i] + nums[i+1] + ... + nums[j]) - (nums[0] + nums[1] + ... + nums[i])
sum_j - sum_i = nums[i+1] + ... + nums[j]
So, when sum_j - sum_i = k, it means the sum of elements from index i+1 to j is equal to k.
This is why in the implementation, we don't need to make any adjustments when we find a match. The current index represents the end of the subarray (j), and the hashmap gives us the count of prefix sums that, when subtracted from the current sum, yield k. Each of these represents a valid subarray ending at the current index.
Unfortunately you really are expected to have seen the question before and memorised the solution. That or you've solved so many similar problems you can use prior experience to solve it. The system is broken, but at least for Meta you know the list of questions ahead of time (the LC list) so you can just practice practice practice the most frequently asked ones.
Thanks for making the videos. Yes I am trying to finish top 75 last 6 months meta questions and see if I can pass phone screening . Never did leet code . But it's the truth , we need to play this game of dsa and algos. Again thanks for making these videos .
@@crackfaang I have 32 years of experience and I was a manager at google. We hired a front end engineer that passed the interview with glory...few weeks later I realized this person did not know anything about front end. I asked to see the loop question.... all leetcode questions... I feel it is like pockets in pijamas ... almost but not totally, useless
i am so confused
idk why this kind of questions are ven asked when there is only one certain to solve this and you are fucked you have not seen the question before.
You could have made that 100X clearer.
Yea this is the shit explanation. My better one for the divisible/equals K problems is in the video for Subarray Sums Divisible By K. It's one of those where if you know how it works it all makes sense but explaining it is harder than learning it lol
[1,1,1] .. i can have element 0 and 1 =2, element 1 and 2 = 2 as you said.. but I also can add the element 0 and 2 and have 2... so 3 sub-arrays not 2. The description of this exercise sucks