L9. Binary Subarrays With Sum | 2 Pointers and Sliding Window Playlist
Notes/Codes/Problem links under step 10 of A2Z DSA Course: takeuforward.org/strivers-a2z...
Entire playlist: • Two Pointer and Slidin...
Follow us on our other social media handles: linktr.ee/takeuforward
Пікірлер: 72
This is an Excellent Question, truly amazing tutorial striver. Kudos to you bro. Striver only heap and stack queues are left, hoping to get those series soon. Take care of your health bro. The entire DSA community will forever be indebted to you.
It becomes hard problem when we try to solve using sliding window but how easily Striver was able to explain it is just Awesome and much appreciated❤❤❤
just a small correction in first while condition r should less only size not equal to while(r
@Funzee
Ай бұрын
do u know where is the article of this code
@moonlight-td8ed
Ай бұрын
@@Funzee there isnt one i guess
Amazing ❤ love your teaching style and love how you teach us how to think from the scratch ❤
best series on sliding windows. thanks a lot.
Understood. While solving this with the sliding window, I got the wrong answer and wondered why. Thanks for the explanation.
Code : class Solution { public: int lessequaltok(vector& nums,int goal){ if(goal return 0; int l = 0; int r = 0; int ans = 0; int n = nums.size(); int sum = 0; while(r sum += nums[r]; while(sum > goal){ sum -= nums[l]; l++; } ans += (r-l+1); r++; } return ans; } int numSubarraysWithSum(vector& nums, int goal) { return lessequaltok(nums,goal)-lessequaltok(nums,goal-1); } };
Long time I was waiting to get these types of problems...good one...
thanks a lot ❤❤
Understood,Thanks striver for this amazing video.
thanku striver bhaiya🙂🙂
understood, thank you
Brilliant 🤯
UNDERSTOOD...Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
amazing
incredible
superb
I never thought of a solution this way. Awesome
Just Wowww!
the solution is amazing ...opened up my mind..superb explanation but i wonder striver did it so easily when will i be able to build such intuition ... i got great confidence throughout the playlist but the way sir brought up the solution amazed me but also gave lot of questions as to when will i be able to think like this
@jritzeku
21 күн бұрын
Honestly for subarray sum problems having negative values or 0s , prefixSum is the way to go. It's slightly less performant but more intuitive. I tried learning the optmized approach several times but its too clever and unlikely to come up with during interview given that we have so many other data structures, algs patterns to worry about already lol. Problems w/ prefixSum: subarray sum equals k, binary sum equals k , nice subarrays(SAME logic as binary sum w/ slight change).
Thanks a ton ❤
At 16:15 I am getting problem here. Why are we considering all the count of r-l+1 when we only get 1 count instead of 4 in the case of 1001? The same problem got reflected in leetcode too, getting wrong answer in test cases. Solution: watch lecture 11 to understand in detail. The code is correct if goal is
Understood. Thanks!
understood
Awesome bhai. Understood.
striver thanks!
how did you get the intution of using this approach
class Solution { public: int count(vector& nums, int goal) { int left = 0; int right = 0; int sum = 0; int count = 0; // if() while (right sum += nums[right]; while (sum > goal && left
in my entire lifetime I will never be able to come to this solution by my own
@jritzeku
24 күн бұрын
And thats completely fine. Consider them as like Mathematical formulas. Recall that without having learned formulas, it would be nearly impossible to solve even simple math problems. Unfortunately these patterns are not covered in traditional CS curriculums where we just learn data structures, and common algorithms like traversals ,insertions ,deletions. Also another common pattern/strategy is to use the prefixSum solution. You shouldn't feel like you have to come up with these patterns on your own...just like math formulas lol.
@devanshsingh2
9 күн бұрын
@@jritzeku Thanks for the motivation dude 🥲😊
Why there is no code
How will we identify if the question is of this type ? or normal sliding window?
@KartikeyTT
28 күн бұрын
this type -> we have to count the no of subarrays normal sliding windows -> we have to find longest length subarray watch video 1 of the playlist and refer type 2 and type 3 problems in the vid
why you added r-l+1 , why not +1
class Solution { public: int fun(vector& arr, int goal){ if(goal int l = 0, r = 0 , cnt = 0; int sum = 0; while(r sum += arr[r]; while(sum > goal){ sum -= arr[l]; l++; } cnt += r - l + 1; r++; } return cnt; } int numSubarraysWithSum(vector& nums, int goal) { return fun(nums,goal) - fun(nums,goal - 1); } };
super anna super logic what is vision what a thought
Here is the solution class Solution { public: int Calculate(vector& nums, int target) { int front=0; int end=0; int count=0; int sum =0; if(target
Shouldn't the complexity be O(n^2) and not O(2*n)
Thanks for the tutorial but, this gives result for
this is the solution that raj bhaiya told us do at last goal-goal-1; class Solution { public: int numSubarraysWithSum(vector& nums, int goal) { int l=0; int r= 0; int count =0; int sum = 0 ; while(r sum = sum+ nums[r]; while(sum>goal){ sum = sum -nums[l]; l++; } if(sum
class Solution { public int helpMe(int[] nums,int goal){ int l=0; int r=0; int sum=0; int cnt=0; if(goal
@chakrabarti9634
3 ай бұрын
Why goal - goal-1 please help😊
@Rahul_Mongia
Ай бұрын
@@chakrabarti9634 Dekh bhai example se samjthe hai let goal=2 Calculate helpMe(nums, goal) This function will count all subarrays with sums less than or equal to 2. Subarrays with sum 0: [] Subarrays with sum 1: [1], [0], [1], [0], [1], [1,0], [0,1], [1], [1,0] Subarrays with sum 2: [1,0,1], [0,1,0], [1,0,1], [1,0], [0,1,0,1], [1,0,1], [1,0,1] Calculate helpMe(nums, goal - 1) This function will count all subarrays with sums less than or equal to 1. Subarrays with sum 0: [] Subarrays with sum 1: [1], [0], [1], [0], [1], [1,0], [0,1], [1], [1,0] Find the Exact Count The number of subarrays with sum exactly 2 is helpMe(nums, 2) - helpMe(nums, 1). Aya samjh....
r less than n not r less than equal to
here is the c++ code; class Solution { public: // it will calculate for
Striver be like ----goli ki speed se videos upload kr dunga.😂❤
It becomes hard problem when we try to solve using sliding window but for you everything is so easy ,how we can think like you
But how to return this value in function in leetcode, wont it be recursive?
@ajithshetty1684
Ай бұрын
class Solution: def numSubarraysWithSum(self, nums: List[int], goal: int) -> int: def fun1(nums,goal): if goal return 0 l = 0 r = 0 sum = 0 cnt = 0 while r goal: sum = sum-nums[l] l=l+1 cnt+=r-l+1 r=r+1 return cnt return fun1(nums,goal)-fun1(nums,goal-1)
Solution using the same method as L7 TC: O(2*n) SC: O(n) in worst case ``` int numSubarraysWithSum(vector& nums, int goal) { int i, j, sum, count, n = nums.size(); queue mq; i = j = sum = count = 0; int k = goal > 0 ? 1 : 0; while(j { sum += nums[j]; if(nums[j] == k) mq.push(j); while(sum > goal) { sum -= nums[i]; if(nums[i] == 1) mq.pop(); ++i; } if(sum == goal) { if(goal > 0) count += mq.front() - i + 1; else count += j-i+1; } ++j; } return count; } ```
class Solution { public: int ans(vector& nums, int goal){ if (goal
anyone fix this class Solution { public int numSubarraysWithSum(int[] arr, int k) { int n = arr.length, count = 0, sum = 0, r= 0, l = 0; while(r sum += arr[r]; while(sum > k){ sum -= arr[l]; l++; } if(sum == k){ count += r - l + 1; } r++; } return count; } }
@tejaswaniguttula5961
3 ай бұрын
@abhaysinhgaikwad Hi brother, class Solution { public int func(int[] arr, int k) { int sum = 0, l = 0, r = 0, count = 0; if (k while (r sum += arr[r]; while (sum > k) { sum -= arr[l]; l++; } if (sum
public int numSubarraysWithSum(int[]nums,int goal){ int prefixZero=0,sum=0,ans=0,i=0,j=0; while(j
its not working for nums = [0,0,0,0,0] goal = 0
@saikumarpeddineni
2 ай бұрын
No it works in this case too
@raparthipranay785
Ай бұрын
Yeah
it should be r
@manikanta6183
3 ай бұрын
Since the array is 0-Indexed. Indexing -> 0,1,2,3 for example nums = {6,4,3,7} nums.size() would be 4, So ultimately we would be accessing the index which is out of bounds
@KartikeyTT
3 ай бұрын
@@manikanta6183 yeah thats what i meant
@manikanta6183
3 ай бұрын
@@KartikeyTTMy bad, I thought you were asking the question 😂
@KartikeyTT
3 ай бұрын
@@manikanta6183 haha
I am watching and I understand the code. But I can't give you a like on Instagram. Instagram use hi nahien krta apka bhai.
import java.util.HashMap; class Solution { public int numSubarraysWithSum(int[] nums, int goal) { int sum = 0; int count = 0; HashMap prefixSums = new HashMap(); prefixSums.put(0, 1); // There's one way to have a sum of 0, by taking no elements. for (int num : nums) { sum += num; // If sum - goal has been seen before, it means there's a subarray ending at the current index // which sums to the goal. if (prefixSums.containsKey(sum - goal)) { count += prefixSums.get(sum - goal); } // Add the current sum to the map of prefix sums. prefixSums.put(sum, prefixSums.getOrDefault(sum, 0) + 1); } return count; } }
Why can't we use this solution for the original subarray problem without binary elements?
@sumitdas2147
26 күн бұрын
Well, I had the same doubt, I realized that in the original problem, the goal or K can be negative. This algorithm fails to handle negative sum value. Also try dry running for this case {-1, -1, 1} with k = 0, you will get the answer as zero. But the correct answer should be 1. Why this algorithm fails? It is because the overall sum b/w left & right can be less than K, but the current element pointed by right is where we are not sure of it, whether it is less than equal to K or not. And this algo add that case in the overall count. Basically, this algo fails to handle negative integers. If someone has a better explanation, please continue this thread.