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.
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
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
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
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.
I solved this question on leetcode with exactly the same code as leetcode 560 (ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-fFVZt-6sgyo.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?
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
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
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.
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
@@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
@@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
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
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; } }
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
