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❤❤❤
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.
if anyone is unable to understand why fun(nums,goal) - fun(nums,goal-1) works here? What's the math here? I am unable to understand this basic maths behind it, please can anyone explain me the maths behind this? Answer : (if you read below example definetly u can understand) Example: Counting people by weight categories Imagine you have a group of people, and each person has a specific weight. You want to know how many people weigh exactly 70 kg. Step 1: Count all people weighing less than or equal to 70 kg This will include people who weigh: Less than 70 kg (like 60 kg, 50 kg, etc.) Exactly 70 kg Let’s say we count all the people who weigh 70 kg or less: There are 25 people who weigh 70 kg or less. We can represent this as fun(weights, goal=70) = 25. Step 2: Count all people weighing less than or equal to 69 kg Now, let’s count all the people who weigh 69 kg or less. These are people who weigh: Less than 70 kg (like 69 kg, 60 kg, 50 kg, etc.) But not those who weigh exactly 70 kg. Let’s say there are 18 people who weigh 69 kg or less. We can represent this as fun(weights, goal=69) = 18. Step 3: Subtract the two results To find out how many people weigh exactly 70 kg, we subtract: fun(weights, goal=70) (people weighing 70 kg or less) = 25 fun(weights, goal=69) (people weighing 69 kg or less) = 18 The number of people who weigh exactly 70 kg is: 25 - 18 = 7 people. General Formula: fun(weights, goal) counts how many people have a weight less than or equal to the goal (here, 70 kg). fun(weights, goal-1) counts how many people have a weight less than or equal to goal - 1 (here, 69 kg). By subtracting the two, you get the number of people who weigh exactly the goal weight. Why it works: This technique isolates the exact count of people (or items) at the goal value by subtracting the number of items below the goal from the number of items less than or equal to the goal. It's easier than directly counting "exact" matches in some problems, which is why this approach is useful.
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).
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
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
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); } };
I am unable to understand why fun(nums,goal) - fun(nums,goal-1) works here? What's the math here? I am unable to understand this basic maths behind it, please can anyone explain me the maths behind this?
please watch A - B in this video ( th-cam.com/users/shorts3uaVqX5qClg?si=c2yO4X4gQwXrqm3u ) continue reading after watching the video. draw the venn diagram of A-B on paper and refer to it while reading this comment for better understanding. lets assume you need people who have 2 rupees that is ( fun(nums,goal) here we are finding people who
@@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....
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
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.
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
class Solution { public int numSubarraysWithSum(int[] nums, int goal) { int i=0, j=0, subArrayCount =0, sum =0; int tempI =0,tempSum =0; while(jgoal){ sum = sum - nums[i]; i++; tempI = i; } tempSum = sum; while(tempSum==goal && tempI
@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
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
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; } }
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.
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
Never in my dreams would have thought of such an ingenious solution. Wow.
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❤❤❤
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.
Great
I was stunned when I saw this approach and realised this type of content was not available in the premium videos.
The most optimal solution is a very great concept and will help you solve many problems in sliding window, even the hard ones......
if anyone is unable to understand why fun(nums,goal) - fun(nums,goal-1) works here? What's the math here? I am unable to understand this basic maths behind it, please can anyone explain me the maths behind this?
Answer : (if you read below example definetly u can understand)
Example: Counting people by weight categories
Imagine you have a group of people, and each person has a specific weight. You want to know how many people weigh exactly 70 kg.
Step 1: Count all people weighing less than or equal to 70 kg
This will include people who weigh:
Less than 70 kg (like 60 kg, 50 kg, etc.)
Exactly 70 kg
Let’s say we count all the people who weigh 70 kg or less:
There are 25 people who weigh 70 kg or less.
We can represent this as fun(weights, goal=70) = 25.
Step 2: Count all people weighing less than or equal to 69 kg
Now, let’s count all the people who weigh 69 kg or less. These are people who weigh:
Less than 70 kg (like 69 kg, 60 kg, 50 kg, etc.)
But not those who weigh exactly 70 kg.
Let’s say there are 18 people who weigh 69 kg or less.
We can represent this as fun(weights, goal=69) = 18.
Step 3: Subtract the two results
To find out how many people weigh exactly 70 kg, we subtract:
fun(weights, goal=70) (people weighing 70 kg or less) = 25
fun(weights, goal=69) (people weighing 69 kg or less) = 18
The number of people who weigh exactly 70 kg is:
25 - 18 = 7 people.
General Formula:
fun(weights, goal) counts how many people have a weight less than or equal to the goal (here, 70 kg).
fun(weights, goal-1) counts how many people have a weight less than or equal to goal - 1 (here, 69 kg).
By subtracting the two, you get the number of people who weigh exactly the goal weight.
Why it works:
This technique isolates the exact count of people (or items) at the goal value by subtracting the number of items below the goal from the number of items less than or equal to the goal. It's easier than directly counting "exact" matches in some problems, which is why this approach is useful.
take it like this , (sum
beautifully explained bro thanks had a confusion intially
Thanks for the explanation!!!
Thanks bro
its basically set theory, you have something like: S
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.
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).
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
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
Can we use the second approach to solve number of subarrays with sum k where the array consists of only positive integers?
No. Of subaarys with sum
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
u should've watched the video till the last
i can stop the video only after listening to that music at the end😁😁
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);
}
};
Thanks striver the solution is cleared.
Damn this was really something 🔥🔥🔥 the day i start thinking like striver cracking google ll be a piece of cake😅
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
wow this made me say wow and when that goal-1 thing again wow
#BHAIYA
I am unable to understand why fun(nums,goal) - fun(nums,goal-1) works here? What's the math here? I am unable to understand this basic maths behind it, please can anyone explain me the maths behind this?
please watch A - B in this video ( th-cam.com/users/shorts3uaVqX5qClg?si=c2yO4X4gQwXrqm3u )
continue reading after watching the video.
draw the venn diagram of A-B on paper and refer to it while reading this comment for better understanding.
lets assume you need people who have 2 rupees that is ( fun(nums,goal) here we are finding people who
if you have 5 $1 candy and 10 $2 candy. Number of candies
UNDERSTOOD...Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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....
@@chakrabarti9634 to find out the exact number of counts equal to sum k.
INSANE BROTHER♥♥
Long time I was waiting to get these types of problems...good one...
thanku striver bhaiya🙂🙂
superb!!!
understood!!!
i tried this approach on number of distinct char in string ==k and it passes only 433/1050 test case then gives tle
thanks a lot ❤❤
here is the c++ code;
class Solution {
public:
// it will calculate for
understood
how did you get the intution of using this approach
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
Brilliant 🤯
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 🥲😊
I never thought of a solution this way. Awesome
understood, thank you
Understood,Thanks striver for this amazing video.
why you added r-l+1 , why not +1
whose brain could have thought like that 🤯
thanks bhaiya
Why there is no code
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
superb
Understood: Big brain time
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;
}
```
Optimal wala to bahut hi jada intuitive hai..
kab pata chalega ki aise bhi solve kar skte hai??
Understood
how it will run for two times ? I can't get it ☹
because you'll call it two times
why did we not solve using prefixSum then?
It can be solved but we want to reduce the space complexity from O(N) which was used in the prefix sum to O(1) .
incredible
Shouldn't the complexity be O(n^2) and not O(2*n)
Awesome bhai. Understood.
amazing
super anna super logic what is vision what a thought
Thanks for the tutorial but, this gives result for
Striver be like ----goli ki speed se videos upload kr dunga.😂❤
class Solution {
public int numSubarraysWithSum(int[] nums, int goal) {
int i=0, j=0, subArrayCount =0, sum =0;
int tempI =0,tempSum =0;
while(jgoal){
sum = sum - nums[i];
i++;
tempI = i;
}
tempSum = sum;
while(tempSum==goal && tempI
Just Wowww!
I will not be able to solve it in one go .
Thanks a ton ❤
Why are we calling it for 2 time ?
Understood. Thanks!
r less than n not r less than equal to
add the code bro pls
and artical also pls
striver thanks!
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)
this video is a little confusing. Watch this again after some time and trust me you will understand much better.
public int numSubarraysWithSum(int[]nums,int goal){
int prefixZero=0,sum=0,ans=0,i=0,j=0;
while(j
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
this is already constant space because we are only increasing the frequency not the element, element can only be 0 and 1, isn't it.
its not working for
nums =
[0,0,0,0,0]
goal =
0
No it works in this case too
Yeah
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.
You can use that. I copy pasted my exact code from that one and it worked in leetcode. The hashing solution I mean.
class Solution {
public:
int ans(vector& nums, int goal){
if (goal
Understood
understood
understood