When I first started DSA, I was just so scared of the code and knowing very little about the logic and the intuition behind but Striver you are the one who has ever showed the completely difference - Extreme natural approach and observation and crystal clear logic. You've made the coding fun and interesting toward people like me. Hats off for your dedication! Understood!
i am doing his dsa sheet , the array part and almost every question has a completely different logic and approach and its becoming quite frustrating as im not able to come up with the solutions so do i just keep solving more problems or am i doing something wrong
Just when I think the video is getting long enough for a simple problem, I go search the web and find not a single tutor with such a powerful explanation!
I saw this video at around 10 am in college, was only able to think of o(n²) solution, I took the pause at your hint of using prefix sum array, kept thinking for some time while in college lectures but was able to get the solution at around 6pm 😝, I know it took time but it felt good to actually think of the solution, please keep up the consistency
This man is my hero, I struggled so much with this question to visualize it and subsequent problems like it. I've done ove 270 LC questions, but this man made it so simple
understood bhaiya . You can not even imagine how much people love u and praise you and speak about your videos all the time. I am sure u get hiccups every now and then . Live long bhaiya u are our real teacher.
Instead of adding 0 in the hashmap, we can just use the statement if(sum==k) ans++; That works fine. See the Below Code int subarraySum(vector& nums, int k) { int ans=0; unordered_map x;
` if(x.find(sum-k)!=x.end()) ans+=x[sum-k]; ` And why this check before incrementing and. class Solution { public: int subarraySum(vector& nums, int k) { int ans=0,sum=0; unordered_map x; for(int i=0;i
So here, if in the question it is stated that it contains only positive as in codestudio then we can apply 2-pointer(Sliding window) as done in longest subarray with sum k. TC: O(N) SC: O(1) Else, if it contains both positive and negative HashMap is optimal
@takeUforward when you explained the logic behind taking the 0 prefix-sum and the count value, my mind was actually blown! This was an amazing explanation, thank you❤
You have given more than anyone can ask for. Thank you for all your support and such amazing videos. They are really helpful. Just a small thing can we have a dark mode setting for "take you forward" pages.
That's really amazing 🤩Striver! code is too sort but logic is superb for the optimal. from brute (TC-> O(N^2), SC -> O(1)) to optimal (TC -> O(N) when using unordered_map, O(N * log N) when using ordered map, SC -> O(N) for using map data structure.
What an excellent explanation! Even after watching another video 6-7 times, l could not understand it. But understood this perfectly after watching only once!
we can also use sliding window 2 pointer approach for this one code-> int findAllSubarraysWithGivenSum(vector < int > & arr, int k) { int n =arr.size(),sum = 0,cnt = 0,left = 0; for(int right = 0;right k) sum-=arr[left++]; if(sum == k) cnt++; } return cnt; }
mpp[0] = 1 helps us to take the count when (sum == k ). Because when sum will be k, then remove will be 0. And then mpp[1] will give us 0, which will be added to the count. If we don't store 0 to our map. then we need to handle the case in an extra if condtion. which is if(sum == k) count++;
The sliding window approach actually performs better with O(n) time complexity. int subarraySum(vector& nums, int sum) { int count = 0; int currSum = 0; unordered_map sumFreq; for (int i = 0; i < nums.size(); ++i) { currSum += nums[i]; if (currSum == sum) count++; if (sumFreq.find(currSum - sum) != sumFreq.end()) count += sumFreq[currSum - sum]; sumFreq[currSum]++; // If currSum becomes greater than sum, // subtract elements from the start while (currSum > sum) { currSum -= nums[i - count + 1]; sumFreq[currSum]--; if (sumFreq[currSum] == 0) sumFreq.erase(currSum); count--; } } return count; }
More optimal solution than striver's: Using two pointers create your imaginary window. If the `sum == k` then increment `count` and move first pointer forward because you no longer need that element to count towards the sum. If `sum > k` then decrease the sum by moving the first pointer forward. If `sum < k` then increase the sum by using the second pointer. If the second pointer has gone out of range start decreasing the window size by incrementing the first pointer. int findAllSubarraysWithGivenSum(vector& arr, int k) { int count = 0; int i = 0; int j = 1; int sum = arr[i]; while(i
Excellent explanation yaar! Great to see such kind of explanations that guide from brute force to optimised solution in such a detail! Thank you so much and keep making such great videos :)
Bhaiya ye Question ka video dekhne se phale hoo gaya 😁😁Only Minor change int findAllSubarraysWithGivenSum(vector < int > & nums, int k) { int right = 0; int left = 0; int count = 0; long long sum = nums[0]; int n = nums.size(); while(right < n){ while(left k){ sum = sum - nums[left]; left++; } if(sum == k){ count++; } right++; if(right < n){ sum+=nums[right]; } } return count; }
It seems like you have edited your voice in the video and made it soft, I am missing that bold voice which is there in the DP playlist. Please don't edit your voice, you don't have to adjust yourself for us. We like the way you are, the original STRIVER🔥🔥
Regarding putting (0,1) int the Hashmap initally : Let consider somehow the preSum got exactly equal to our k, means now the sub-array till that presum element gives us the k (~ preSum-k = 0). means whenever we find our preSum touching the k value, we need to increment count but we will not be able to find it in hashMap as it is yet to be inserted that why either increment count based on if preSum-k = 0 or put a (0,1) in hashmap to automatically finding preSum-k = 0 in the hashMap. int preSum = 0, count = 0, start = 0; Map mp = new HashMap(); for(int i=0;i
My optimized Code different from the given optimized code, with same time complexity : int subArraySumOptimized(vector &nums, int k) { int n = nums.size(); int summation = 0; map mpp; int count = 0; for (int i = 0; i < n; i++) { summation += nums[i]; if (summation == k) { count++; } if (mpp.find(summation - k) != mpp.end()) { count += mpp[summation - k]; } mpp[summation]++; } return count; }
Storing (0,1) in the hashmap is bit confusing, instead we can just increase a check i.e. if(currSum == k) count++. The more readable code(JAVA) will look like this: public int subarraySum(int[] nums, int k) { int currSum = 0, count = 0; int n = nums.length; HashMap map = new HashMap(); for(int i=0; i
Without adding to map, you need to count occurrences still not in map public int subarraySum(int[] nums, int k) { int sum=0; int count =0; Map map = new HashMap(); for(int i=0;i
❓ You mentioned performing a dry run on the array [3, -3, 1, 1, 1] to understand the significance of initially putting (0, 1) in the map. However, it hasn't been specified which sum we should consider for this particular dry run.
Although i understood, if we didn't want to put initially that or if we find it challenging to understand its significance. there is an alternative approach to handle the situation. Another way is when currentSum - given_sum == 0 we just need to increment counter. that's it we can omit to put initially (0,1) pair in map.
Easy to understand code #include int findAllSubarraysWithGivenSum(vector < int > & arr, int k) { // Write Your Code Here map mpp; int sum=0; mpp[0]=1; int count=0; for(int i=0;i
Literally, maybe just because I'm watching while I'm not in complete attention but still the optimal approach feels like it comes with a completely different path as compared to normal intuitive thought process
When I first started DSA, I was just so scared of the code and knowing very little about the logic and the intuition behind but Striver you are the one who has ever showed the completely difference - Extreme natural approach and observation and crystal clear logic. You've made the coding fun and interesting toward people like me. Hats off for your dedication! Understood!
i am doing his dsa sheet , the array part and almost every question has a completely different logic and approach and its becoming quite frustrating as im not able to come up with the solutions so do i just keep solving more problems or am i doing something wrong
keep going! I was in the same boat, you'll slowly be able to form logic@@utkarshverma3314
@@utkarshverma3314 same problem i am also facing
ashishbhattacharyya yup, it works for me.
could you please tell if i should make notes ?? how do i make them so that i dont put hours in it
Just when I think the video is getting long enough for a simple problem,
I go search the web and find not a single tutor with such a powerful explanation!
I saw this video at around 10 am in college, was only able to think of o(n²) solution, I took the pause at your hint of using prefix sum array, kept thinking for some time while in college lectures but was able to get the solution at around 6pm 😝, I know it took time but it felt good to actually think of the solution, please keep up the consistency
This man is my hero, I struggled so much with this question to visualize it and subsequent problems like it. I've done ove 270 LC questions, but this man made it so simple
understood bhaiya . You can not even imagine how much people love u and praise you and speak about your videos all the time. I am sure u get hiccups every now and then . Live long bhaiya u are our real teacher.
I saw many times but I couldn't understand...But now i finally understood and realised that ur explaination is too good...!
Instead of adding 0 in the hashmap, we can just use the statement if(sum==k) ans++; That works fine.
See the Below Code
int subarraySum(vector& nums, int k)
{
int ans=0;
unordered_map x;
int sum=0;
for(int i=0;i
very good .
` if(x.find(sum-k)!=x.end()) ans+=x[sum-k]; `
And why this check before incrementing and.
class Solution {
public:
int subarraySum(vector& nums, int k)
{
int ans=0,sum=0;
unordered_map x;
for(int i=0;i
brilliant
It will fail for the test case: [1,-1,0] k = 0.
So here, if in the question it is stated that it contains only positive as in codestudio then we can apply 2-pointer(Sliding window) as done in longest subarray with sum k. TC: O(N) SC: O(1)
Else, if it contains both positive and negative HashMap is optimal
Timestamps
01:03 - Problem Statement
01:13 - Sub-array definition
01:52 - Example
03:13 - Brute force solution
06:07 - Complexity
06:29 - Better solution
08:07 - Complexity
08:21 - Optimal Solution
08:41 - Prefix sum concept
09:35 - Example
13:55 - Dry run
21:22 - Code
22:38 - Complexity
@takeUforward when you explained the logic behind taking the 0 prefix-sum and the count value, my mind was actually blown! This was an amazing explanation, thank you❤
Its really amazing that you are taking your time in explaining via the dry run. It helps me a lot. Thanks :)
You have given more than anyone can ask for. Thank you for all your support and such amazing videos. They are really helpful. Just a small thing can we have a dark mode setting for "take you forward" pages.
You can build one chrome extension may be ;)
appreciates striver by telling "u have given more than anyone can ask" and proceeds to place demand .
@@takeUforward lol would be a good project for the resume?
striver actually give the dark mode option
That's really amazing 🤩Striver! code is too sort but logic is superb for the optimal. from brute (TC-> O(N^2), SC -> O(1)) to optimal (TC -> O(N) when using unordered_map, O(N * log N) when using ordered map, SC -> O(N) for using map data structure.
Struggled to understand this solution, now understood, Keep up the great work Striver
This explanation is so 100x better than Neetcode's. Thank you !!!
What an excellent explanation! Even after watching another video 6-7 times, l could not understand it. But understood this perfectly after watching only once!
we can also use sliding window 2 pointer approach for this one code->
int findAllSubarraysWithGivenSum(vector < int > & arr, int k) {
int n =arr.size(),sum = 0,cnt = 0,left = 0;
for(int right = 0;right k) sum-=arr[left++];
if(sum == k) cnt++;
}
return cnt;
}
It will fail .arr[]=[1] k=0
@@amitranjan6998 yes we just need to add a condition of left
Thank you so much. I saw many other youtuber's video but this video is the best . I was able to understand after watching this video for 2 times
mpp[0] = 1 helps us to take the count when (sum == k ). Because when sum will be k, then remove will be 0. And then mpp[1] will give us 0, which will be added to the count. If we don't store 0 to our map. then we need to handle the case in an extra if condtion. which is if(sum == k) count++;
Understood Striver ❤. You are a living legend sir. 🤩🤩
The sliding window approach actually performs better with O(n) time complexity.
int subarraySum(vector& nums, int sum) {
int count = 0;
int currSum = 0;
unordered_map sumFreq;
for (int i = 0; i < nums.size(); ++i) {
currSum += nums[i];
if (currSum == sum)
count++;
if (sumFreq.find(currSum - sum) != sumFreq.end())
count += sumFreq[currSum - sum];
sumFreq[currSum]++;
// If currSum becomes greater than sum,
// subtract elements from the start
while (currSum > sum) {
currSum -= nums[i - count + 1];
sumFreq[currSum]--;
if (sumFreq[currSum] == 0)
sumFreq.erase(currSum);
count--;
}
}
return count;
}
But the thing is sliding window approach won't work for negative numbers
@@ritu-ql8fk Just remove the extra while loop
Finally understood the prefix sum concept after u explained by doing a dry run! Thanks Striver!❤✌🏼
16:29 if we write if(sum==k) count++
We don't need to include 0 at beginning
good one!!
THAT IS WHAT I WAS DOING
thank you
More optimal solution than striver's:
Using two pointers create your imaginary window. If the `sum == k` then increment `count` and move first pointer forward because you no longer need that element to count towards the sum. If `sum > k` then decrease the sum by moving the first pointer forward. If `sum < k` then increase the sum by using the second pointer.
If the second pointer has gone out of range start decreasing the window size by incrementing the first pointer.
int findAllSubarraysWithGivenSum(vector& arr, int k) {
int count = 0;
int i = 0;
int j = 1;
int sum = arr[i];
while(i
It will work only for non negative numbers in array.As u are moving forward assuming that sum will not decrease,think about it
@@mythologyKnowledge6581 Yeah, you 're right. It's only optimal for positives.
Understood Bhaiya! This was a tough one to understand for me...will soon revisit it
Thank you🙏
you are topG of DSA
Amazingly Understood, Thank you for such a in depth thought process
Excellent explanation yaar! Great to see such kind of explanations that guide from brute force to optimised solution in such a detail! Thank you so much and keep making such great videos :)
God for beginner❤hats of u bhaiya
Understood! Super fantastic explanation as always, thank you very very much for your effort!!
class Solution {
public:
int subarraySum(vector& nums, int k) {
int psum=0,e=0,count=0;
unordered_maphashmap;
hashmap[0]=1;
while(e
Previous explanation and current explanation is good .understood
Bhaiya ye Question ka video dekhne se phale hoo gaya 😁😁Only Minor change
int findAllSubarraysWithGivenSum(vector < int > & nums, int k) {
int right = 0;
int left = 0;
int count = 0;
long long sum = nums[0];
int n = nums.size();
while(right < n){
while(left k){
sum = sum - nums[left];
left++;
}
if(sum == k){
count++;
}
right++;
if(right < n){
sum+=nums[right];
}
}
return count;
}
It seems like you have edited your voice in the video and made it soft, I am missing that bold voice which is there in the DP playlist. Please don't edit your voice, you don't have to adjust yourself for us. We like the way you are, the original STRIVER🔥🔥
But we need to look at the future, we want to go global, so audio quality has to be maintained, I hope you get that :)
@@takeUforwardand we love you for that too,
It's sort of unconditional 😂
Banee...
I think I should watch it again, have watched a lot of your video this is the first which I didn't understand in the first go.
thanks striver you have really explained this so well
god bless you
you are a wonderful teacher for many 🙏🙏
Excellent explanation, understood ! ✨
Was able to think O(N^2) approach and totally underatood optimal solution too 😊
Hi bhaiya it would be really helpful if you can give similar question links for practise after every question explanation!!
Regarding putting (0,1) int the Hashmap initally :
Let consider somehow the preSum got exactly equal to our k, means now the sub-array till that presum element gives us the k (~ preSum-k = 0).
means whenever we find our preSum touching the k value, we need to increment count but we will not be able to find it in hashMap as it is yet to be inserted that why
either increment count based on if preSum-k = 0 or put a (0,1) in hashmap to automatically finding preSum-k = 0 in the hashMap.
int preSum = 0, count = 0, start = 0;
Map mp = new HashMap();
for(int i=0;i
Striver you are great 🙌🙌 .I just want to thank you ❤️.
Really good explanation & kudos to efforts, understood 👍
Striver you can make these playlists a bit fun if you allow your viewers to suggest you problems they think discussable !!
btw loving the playlist
Plz don't ruin it for us 😂😂😂
plz no
Understood. Thank you so much!
though I am still figuring out on the map[0]=1 part but surely the rest of the part was indeed clear. thanks for these videos.
if you select no element in sub array then , map[0]=1
We can also solve this problem in O(1) space complexity but the T.C will be 2N using two pointer approach.
for me optimal is little hard but after see 2-3 time video , got easly understand
understood captain...thanks
Understood💖amazing explanation
if instead of specifying map[0]=1 in the beginning if we give a condition that if(preSum == k) { count ++;}
Will it be correct Striver bhaiya??
My optimized Code different from the given optimized code, with same time complexity :
int subArraySumOptimized(vector &nums, int k)
{
int n = nums.size();
int summation = 0;
map mpp;
int count = 0;
for (int i = 0; i < n; i++)
{
summation += nums[i];
if (summation == k)
{
count++;
}
if (mpp.find(summation - k) != mpp.end())
{
count += mpp[summation - k];
}
mpp[summation]++;
}
return count;
}
i still don't get the significance of (0,1) in the map, my answer still got submitted in Leetcode.
Thank you Striver. I owe you❤
That Dry run! 🔥
Thanks for the great video. I don't see how I can come up with the optimal solution during the interview without hint from the interviewer.
solution blew my mind
Storing (0,1) in the hashmap is bit confusing, instead we can just increase a check i.e. if(currSum == k) count++. The more readable code(JAVA) will look like this:
public int subarraySum(int[] nums, int k) {
int currSum = 0, count = 0;
int n = nums.length;
HashMap map = new HashMap();
for(int i=0; i
tks for explanation, you are savior
Without adding to map, you need to count occurrences still not in map
public int subarraySum(int[] nums, int k) {
int sum=0;
int count =0;
Map map = new HashMap();
for(int i=0;i
Awesome explanation, one approach of sliding window will not work in this problem if array contains negative elements also.
you are awesome bhaiya...
understood ,thnx for amazing video ❤❤❤❤❤❤
Understood ❤️
Understood 💯💯💯
❓
You mentioned performing a dry run on the array [3, -3, 1, 1, 1] to understand the significance of initially putting (0, 1) in the map. However, it hasn't been specified which sum we should consider for this particular dry run.
Although i understood,
if we didn't want to put initially that or if we find it challenging to understand its significance.
there is an alternative approach to handle the situation.
Another way is when currentSum - given_sum == 0 we just need to increment counter.
that's it we can omit to put initially (0,1) pair in map.
Thanks for the help raj bhaiya
understood sir ,great explanation
Can you pls pls plsssss do strings before binary search next plsss🙏 ? From 2023 batch🥺. Wish we could have the entire series in our 1st 2nd 3rd yrs
Great one ! ❤
Awesome Awesome Sir...............
Thanks bhaiya, understood
Can also do like this:
int subarraySum(vector& nums, int k) {
unordered_map m;
int c = 0;
int s=0;
for(int i=0;i
Easy to understand code
#include
int findAllSubarraysWithGivenSum(vector < int > & arr, int k) {
// Write Your Code Here
map mpp;
int sum=0;
mpp[0]=1;
int count=0;
for(int i=0;i
U complicated it 😂
thanks really good explination
Understood !! 😍😍
Understood, thank you.
undestood ✌
Understood✅🔥🔥
are we supposed to think of optimal solution on our own. asking because it seems pretty daunting.
Its not daunting, it is basically a technique, on the basis of this you can solve many questions
Literally, maybe just because I'm watching while I'm not in complete attention but still the optimal approach feels like it comes with a completely different path as compared to normal intuitive thought process
Understood 👍
Understood 🙏🏻
Nice explation ❤
Understood, thanks!
What if the array contains 0s?
Understood Sir!
The Best♥
nice ..........explanation
Understood 🎉
Thanks bro. Understood
understood striver thanks
Dronacharya from 21st century!!
Please also make video for count pairs with given sum and divisible by k
very nice. .thankyou
we can also do this problem by sliding window technique
Bro u are looking like virat ❤
22:54 *please explain what lines*
int remove = presum - k;
count += mp[remove];
mp[presum]++;
do ?
thank you so much
i can think of brute and better solution but optimal can't be thought all by myself but is too confusing
UNDERSTOOD
Understood.