Binary Subarrays with Sum - Leetcode 930 - Python

[@oneepicsaxguy6067]

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]

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

[@bearchun]

yes this explanation is wrong. it's not the goal being 0 the issue. the issue is you have 0 in the list of numbers, that is the problem.

[@anirudhjoshi4305]

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

[@EduarteBDO]

is there a way to solve without being cleaver? 😢

[@vasr562]

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

[@oneepicsaxguy6067]

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

[@osazeimohe7269]

If you're comfortable with prefix sums, you can solve it using prefix sums and a hashmap. This solution is a bit tough to come up with lol

[@MangoTroll34]

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

[@SAIGOVINDSATISH]

Finally Sir you are back🎉

[@ronaldmcsidy763]

I hate myself for having to look at the solution 😅

[@MangoTroll34]

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

[@xingyuxiang1637]

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]

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]

You are not alone🥲

[@Butter9322]

Dude this was so not intuitive. Like the sliding window part was obvious, but not getting the difference that was weird.

[@CS_n00b]

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

[@jazzyx95]

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]

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]

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

[@jazzyx95]

​@@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 < end and (nums[start] == 0 or current > 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]

@@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 < end and (nums[start] == 0 or current > 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

[@1vader]

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

[@shankhadeepdas3264]

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

[@jazzyx95]

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

[@jazzyx95]

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.

[@yang5843]

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

[@shekarvalluri6457]

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

[@CS_n00b]

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

[@gismetmajidov]

Really good solution. Brilliant insight!

[@shivanshutripathi8985]

It's a very nice solution. Thanks!!

[@kavyanshbansal5417]

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

[@luciferdesuza1541]

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

[@logchamption]

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

[@shikshamishra5668]

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

[@satyamjha68]

Solved it !! I really liked this problem!

[@franciskp9117]

Genius solution.

[@huyennguyenmaingoc468]

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

[@varunpalsingh3822]

congratulations navdeep for 1 Lakh subscribers 😊

[@NeetCodeIO]

Much appreciated :⁠-⁠)

[@ravirathore6717]

nice explanation good job👍

[@yashsolanki069]

Congratulations on 100k 🎉

[@business_central]

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

[@lan10ak]

Same logic as in Subarray Sum Equals K

[@Shah_73]

congrats for 100k subs!!

[@yang5843]

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 < 0 ) return 0; 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_AM_JD_]

This can't work in brute force n^2

[@1bcx]

Just here to say hello!

[@0xkirti]

wow bilkul samjh nhi aya

[@chien-yuyeh9386]

🎉🎉🎉🎉🎉

[@ssjPotato.]

I solved this question on leetcode with exactly the same code as leetcode 560 (kzbin.info/www/bejne/nHe5i6dja9iar9E), 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?