4:06 is completely wrong (or at the very least very convoluted). The problem is not when the goal=0; it is when currentSum == goal and you encounter 0s. In sliding window, we can either move your left pointer forwards or right pointer forwards but not both. Suppose you have [0, 1, 0] with goal = 1 You can either code for your l, r pointers to behave this way: 0,1 -> 0,2 -> 1,2 (move right first unless sum exceeds or you reach the end) Or: 0,1 -> 1,1 -> 1,2 (move left first until sum remains equal, then move right) In both cases, you're either missing 1,1 or 0,2.

@sagaratla187

4 ай бұрын

You are absolutely right! Unless you write the sliding window yourself, it is not easily intuitive.

Could you please upload the solution for day before yesterday's question ? It was question no. 1171 titled Remove Zero Sum Consecutive Nodes from Linked List

I hate myself for having to look at the solution 😅

@MangoTroll34

4 ай бұрын

Looking at the solution means you are learning something new! That means you are improving!

@xingyuxiang1637

4 ай бұрын

Solutions are others if people cannot solve the problems by themselves. This problem is suspiciously greedy because some solutions use the prefix sum and hashmap at the same time. Recursions that do not return at the leaf node can take time to understand. I think building a game may be easier than grinding. However, the combat system in game development requires asynchronous programming. I would spend less time on greedy problems. A functional project sounds more practical.

@sk_4142

4 ай бұрын

you're supposed to look up the solution if you can't solve it in 30-45 minutes. no point in wasting any more time trying to salvage your ego.

@superlostgamer1608

4 ай бұрын

You are not alone🥲

Thanks for the video! This is an interesting trick. We are calculating (# subarrays

I didn’t follow your argument on why when the goal = 0 the initial solution ran into issues?

Solved it !! I really liked this problem!

Finally Sir you are back🎉

Really good solution. Brilliant insight!

It's a very nice solution. Thanks!!

It is good soln., also can u make a video about disjoint subarray which was asked in leetcode 388 ?

is there a way to solve without being cleaver? 😢

@vasr562

4 ай бұрын

Same, no way I can come up with this solution during an interview

@oneepicsaxguy6067

4 ай бұрын

With a hashmap you can solve it in O(n) as well, in a single pass. Only thing is you're using extra space. Make a map with key=prefixSum, value = number of occurrences of said prefixSum ans = 0 map = {0:1} # initialise with 0 because it represents not removing any element (think 1, 1, 1 with goal=3) for x in array: runningSum+=x if (runningSum - goal) in map: ans += map[runningSum - goal] map[runningSum]++ return ans

Congratulations on 100k 🎉

nice explanation good job👍

congrats for 100k subs!!

I tried the solution you used in LC 560. Subarray Sum Equals K and it worked. I guess we are supposed to use another solution but for everyone who struggled with DP, there are other solutions for you XD

Genius solution.

Can you make for a video for "Remove Zero Sum Consecutive Nodes from Linked List"?

This question is tricky in that the normal version of two pointer will miss some intervals due to existence of 0s. We need to consider the leading 0s in our window. When we have a way of finding leading 0s and our sliding window satisfies the condition. Ans += 1 ( the number itself ) + number_of_leading_zeroes_in_the_window ( it means we can start at each of those position so we get a different subarray ). To achieve this, rather than expanding the right boundary first until condition is broken and then shrink the left boundary. We can shrink the left boundary until condition is not broken and then expand the right boundary. This will give us the leading zeroes. This idea is much easier to reason with compared to the editorial solutions in my opinion.

@aqhr050

4 ай бұрын

Could you maybe share some pseudocode or direction on how we would go about finding the right number of zeros (since not all zeros are the same, if a zero follows a one then it's essential to the minimum sub array that meets the goal and we do not want to double count by considering it a zero outside of the goal meeting minimum sub array). I tried to reason an approach but sadly couldn't hack it

@oneepicsaxguy6067

4 ай бұрын

I don't think this is correct. If you have submitted a working code, please share it here.

@jazzyx95

4 ай бұрын

​@@aqhr050Here it is. Let me know if you have any questions. class Solution(object): def numSubarraysWithSum(self, nums, goal): """ :type nums: List[int] :type goal: int :rtype: int """ # we use sliding window, # to account for all subarrays, # however with binary arrays, including 0s won't change the sum. # eg. [0,[ 0, 0,] 0 .. 1 ...] , the middle interval is missed # we can track the leading zeroes in our window # unlike typical two pointer, when we keep expanding right until condition is broken, then expand left # here we keep expanding left until condition not broken, doing so allows us to track leading zeroes start = 0 leading_zeroes = 0 current = 0 ans = 0 # vice versa for end in range(len(nums)): # [start ..... end] # [0,0,0........0] # put end into our sliding window. so the current sum will monotonically increase current += nums[end] # shrinking the window from left while start goal): # record leading zeroes if nums[start] == 1: leading_zeroes = 0 else: leading_zeroes += 1 # update current and start current -= nums[start] start += 1 # goal detection if current == goal: ans += 1 + leading_zeroes return ans

@jazzyx95

4 ай бұрын

@@oneepicsaxguy6067class Solution(object): def numSubarraysWithSum(self, nums, goal): """ :type nums: List[int] :type goal: int :rtype: int """ # we use sliding window, # to account for all subarrays, # however with binary arrays, including 0s won't change the sum. # eg. [0,[ 0, 0,] 0 .. 1 ...] , the middle interval is missed # we can track the leading zeroes in our window # unlike typical two pointer, when we keep expanding right until condition is broken, then expand left # here we keep expanding left until condition not broken, doing so allows us to track leading zeroes start = 0 leading_zeroes = 0 current = 0 ans = 0 # vice versa for end in range(len(nums)): # [start ..... end] # [0,0,0........0] # put end into our sliding window. so the current sum will monotonically increase current += nums[end] # shrinking the window from left while start goal): # record leading zeroes if nums[start] == 1: leading_zeroes = 0 else: leading_zeroes += 1 # update current and start current -= nums[start] start += 1 # goal detection if current == goal: ans += 1 + leading_zeroes return ans

Interesting but also kinda weird solution. I did a regular sliding window and just added a special case for the goal == 0 case where i compute the count based on contiguous zeroes: if goal == 0: zeroes = 0 count = 0 for n in nums: if n == 0: zeroes += 1 count += zeroes else: zeroes = 0 return count Implementing the sliding window is a bit annoying though, counting the subarrays

first time I have a different solution that I think could be worth sharing. I did prefix sum using hashmap: class Solution: def numSubarraysWithSum(self, nums: List[int], goal: int) -> int: """ prefix sum [1,0,1,0,1] [1,1,2,2,3] prefixmap = {1:2 , 2:2 , 3: 1} #val : count """ prefix = 0 prefixmap = collections.defaultdict(int) res = 0 for n in nums: prefix += n if prefix == goal: res += 1 if prefix - goal in prefixmap: res += prefixmap[prefix - goal] prefixmap[prefix] +=1 # print(prefixmap) return res

User The array consists of n positive integers. The sum of all elements in the array is at most maxSum. The absolute difference between any two consecutive elements is at most 1. what is the maximum value of the integer at index k such an array constraints: 1

One question, for sliding window, why do we keep shrinking left pointer. Rather than keep expanding right pointer?

@jazzyx95

4 ай бұрын

I just tested it, it works with looping over l, and keep expanding r until condition is broken as well. So it's a preference thing.

congratulations navdeep for 1 Lakh subscribers 😊

@NeetCodeIO

4 ай бұрын

Much appreciated :⁠-⁠)

Hello sir, i would be great help if you explain and solve a problem name Minimum difference after removal of elements. Question no was 2163

Can we use this logic for integers values also? Will it work ?

@shikshamishra5668

4 ай бұрын

you can use same method for the problem 560. Subarray Sum Equals K

This is same problem as 560. Subarray Sum Equals K which can be done using hashmaps as taught by you on this channel

Same logic as in Subarray Sum Equals K

Just here to say hello!

res = 0 l = 0 cursum = 0 for r in range(len(nums)): cursum += nums[r] # If the current sum exceeds the goal, move the left pointer to shrink the window while cursum > goal and l

This can't work in brute force n^2

wow bilkul samjh nhi aya

the solution is very great. but i feel insane to devise it.

🎉🎉🎉🎉🎉

Java Solution class Solution { public int numSubarraysWithSum(int[] nums, int goal) { return helper(nums,goal)-helper(nums,goal-1); } int helper(int[] nums, int goal) { if ( goal int sum = 0; int rc = 0; int j = 0; for ( int i=0;i goal ) sum -= nums[j++]; rc += (i-j+1); } return rc; } }

I solved this question on leetcode with exactly the same code as leetcode 560 (kzread.info/dash/bejne/mHqKvNZmZtbNqdI.html), and it accepted it. However, it seems to me that doesn't actually work for all cases where goal = 0. Ex: nums = [0,0,0,0,0,1,0,0,1,0,0], goal = 0. Any idea why leetcode is accepting it? Does the question just not have test cases that are good enough to catch it, or am I misunderstanding and that algorithm actually works?