L9. Binary Subarrays With Sum | 2 Pointers and Sliding Window Playlist
HTML-код
- Опубликовано: 25 мар 2024
- 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
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.
Code :
class Solution {
public:
int lessequaltok(vector& nums,int goal){
if(goal < 0)
return 0;
int l = 0;
int r = 0;
int ans = 0;
int n = nums.size();
int sum = 0;
while(r < n){
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);
}
};
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
do u know where is the article of this code
@@Funzee there isnt one i guess
Amazing ❤ love your teaching style and love how you teach us how to think from the scratch ❤
class Solution {
public:
int count(vector& nums, int goal) {
int left = 0;
int right = 0;
int sum = 0;
int count = 0;
// if()
while (right < nums.size()) {
sum += nums[right];
while (sum > goal && left
Understood. While solving this with the sliding window, I got the wrong answer and wondered why. Thanks for the explanation.
best series on sliding windows. thanks a lot.
thanks a lot ❤❤
understood, thank you
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
class Solution {
public:
int fun(vector& arr, int goal){
if(goal < 0 ) return 0;
int l = 0, r = 0 , cnt = 0;
int sum = 0;
while(r < arr.size()){
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);
}
};
thanku striver bhaiya🙂🙂
Brilliant 🤯
amazing
superb
incredible
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
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).
UNDERSTOOD...Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Long time I was waiting to get these types of problems...good one...
Just Wowww!
here is the c++ code;
class Solution {
public:
// it will calculate for
Understood,Thanks striver for this amazing video.
understood
class Solution {
public int helpMe(int[] nums,int goal){
int l=0;
int r=0;
int sum=0;
int cnt=0;
if(goal
Why goal - goal-1 please help😊
@@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....
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!
I never thought of a solution this way. Awesome
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 < n)
{
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;
}
```
Awesome bhai. Understood.
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 < nums.size()){
sum = sum+ nums[r];
while(sum>goal){
sum = sum -nums[l];
l++;
}
if(sum
striver thanks!
in my entire lifetime I will never be able to come to this solution by my own
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.
@@jritzeku Thanks for the motivation dude 🥲😊
how did you get the intution of using this approach
why you added r-l+1 , why not +1
How will we identify if the question is of this type ? or normal sliding window?
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
Thanks for the tutorial but, this gives result for
r less than n not r less than equal to
class Solution {
public:
int ans(vector& nums, int goal){
if (goal
Why there is no code
Shouldn't the complexity be O(n^2) and not O(2*n)
super anna super logic what is vision what a thought
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
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 < n){
sum += arr[r];
while(sum > k){
sum -= arr[l];
l++;
}
if(sum == k){
count += r - l + 1;
}
r++;
}
return count;
}
}
@abhaysinhgaikwad
Hi brother,
class Solution {
public int func(int[] arr, int k) {
int sum = 0, l = 0, r = 0, count = 0;
if (k < 0) return 0;
while (r < arr.length) {
sum += arr[r];
while (sum > k) {
sum -= arr[l];
l++;
}
if (sum
But how to return this value in function in leetcode, wont it be recursive?
class Solution:
def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
def fun1(nums,goal):
if goal < 0:
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)
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
No it works in this case too
Yeah
it should be r
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
@@manikanta6183 yeah thats what i meant
@@KartikeyTTMy bad, I thought you were asking the question 😂
@@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?
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.