Longest Subarray with sum K | Brute - Better - Optimal | Generate Subarrays
HTML-код
- Опубликовано: 26 авг 2024
- Notes/C++/Java/Python codes:
Longest Subarray with sum K [positives]: takeuforward.o...
Longest Subarray with sum K [positives + negatives]: takeuforward.o...
Problem links.
Longest Subarray with sum K [positives]: bit.ly/3GHyBOS
Longest Subarray with sum K [positives + negatives]: bit.ly/3mNSZ9u
We have solved the above problems, and we have gone from brute force and ended with the most optimal solution.
Full Course: bit.ly/tufA2ZYt
You can follow me across social media, all my handles are below:
Linkedin/Instagram/Telegram: linktr.ee/take...
0:00 Introduction of course
Let's march ahead, and create an unmatchable DSA course! ❤
Timestamps pleaseeee
Use the problem links in the description.
Thanks for your effort ❤️
Bhaiya how can I keep that check marks permanently... because it always get cleaned up 😩
@@factsmadeiteasy9943 bro history ya cookies clear mat karo tumhari progress cookies me save hoti hai...
@@leoved1073 oh thanks bro 👍🏻
i think that this problem could be done by just using hashmap.
I've been watching this lecture for the last two days, and it was so frustrating that I couldn't understand the concept, even though Raj Bhaiya explained it thoroughly. After putting in about 7-8 hours, I finally understood what was holding me back. Here's what I've learned:
1. map_name.find(value)-> This function returns an iterator to the element with the key `value` if it is present in the map. If the key is not found, it returns an iterator to `map_name.end()`.
2. map_name.end()-> This function returns an iterator one past the last element of the map. If your map has a size of 4 (indexing from 0 to 3), `map_name.end()` will give you an iterator representing index 4, which is beyond the last element.
3. if(map.find(value) != map.end())-> This line was a real pain in my ass so basically this line checks whether the key `value` is present in the map. If `map.find(value)` does not equal `map.end()`, it means the key is found in the map.similarly , if `map.find(value)` equals `map.end()`, the key is not present in the map.
Understanding this line was crucial for me. The `.find()` function returns an iterator to the element if it is present, or `map.end()` if it is not. So, the condition `if(map.find(value) != map.end())` essentially means, "if the key `value` is found in the map."
If you've read this far, all the best, buddy! I was literally crying inside after watching the video again and again, but if a noob like me can understand it, you will definitely nail it. Haha. Thanks, Raj Bhaiya.
❤
Proud of your efforts bud ❤ let's keep going
Thanku this helped a lot
thanks a lot bro, im on the hard section rn and was stuck on the longest zero sum problem and i found this!
you stuck over the thing where map comes....i cant even get the approach ...ye longest subarray ka approach hi nhi ghus rha bhaiii
Thanks a lot buddy!
When Striver says no one will teach you in such depth, he means it
To all those whose mind are like " shyd coding is not for me" after seeing this question
Take my one advice am the one solving it from 11 :am in the morning and understood it at 7 20 pm of evening
I between my mind qas like chod de "pr bhaiya chodna hi toh nhi hai tabhi toh smjega"
So give yourself a shootout and say striver bhaiya i will play you once more and play it back to back even if you have watched for 100 times play it slowly took a pen copy and try to understand what bhaiya is saying 🎉🎉
was literally feeling the same, but you sowed a new hope in me
thanks for this comment !!!instilled hope in me.
cringe
🥺🥺
i am abouve to change a someone else video but you give me hop
I am following your playlist for DSA. I got subarray of string related problem in my JP Morgan interview. I have explained the approach as you taught. It was quite simple for me to explain the approach as I had watched your this video.. Thank you so much sir you are doing very well.
did u get into jp morgan?
That hashing one went above my mind maybe need to watch it again
Fr may be after few days
TIMESTAMPS
0:00 Intro
0:43 Problem Explanation
3:37 Brute force approach
10:50 Better approach (Both positives + negatives)
26:57 Time complexity of Hashing based better solution and why its best for both positives and negatives
28:55 Optimal solution (positives only)
37:52 Time complexity of two pointer based optimal solution
thanks dude
Thank you bro
Striver please add this so everyone wud be get useful of this
thanks bhai
Please keep this series continued. Brilliant work Raj. I am speechless. An if anyone reading this, and you have a difficulty understanding, don't give up, just watch 2-3 more times, you shall understand, trust me.
LOL, I came back today and now the things are getting cleared.
@@Akash-yr2ifyeah!!
thats the spirits boys, lets goooooo !!!!!!!!
for one question , 3 hours
is it a joke
You are helping families not individuals. Thanks for this.
Thank you striver for this ultimate course, I was trying from many days and searching to starts DSA, and this course made me do it
Today day 15 😅
hello bhai apki growth kaisi hai abhi kya question ban rhe mai beigner hu mujse to easy bhi nhi ho rhe hai kitna time spend karna chiye ek question mai
@@akworld2739 same goes for me . ab ban rahe hai kya bhai questions ?
Those who understand the beauty of ur optimal codes, will agree, ALL UR LEC.S ARE PURE GOLD.
U are a gr8 GURU .... sharing such exceptional lec.s for free is superb SERVICE FOR MANKIND.
U are empowering youth ... making difficult topics look like easy ....
u explain everything so easilty ... study looks like fun when u teach.
Codes can revolutionise the world ... can take us to distant planets....
Codes are like miracle ... the way incredible creation like AI is developed .... Sw Er.s are next Gen soldiers of nation.
They can fuel engine of growth and contribute in development of nation and growth of humanity.
U r doing exceptional work ... Thank for evth..... God bless u ... Tc.
Had to watch it twice to understand it like 95% but did understand it.
Really impressive stuff!
It's easy if you do a dry run on yourself
@@takeUforward yes I was also confused but when I did the Dry run I got it.
Mujhe both positive and negative ka optimal samajh hi ni aaya, like approach I understood in one go and found it very easy. But code ni smjh aaya 2 baar dekhne par bhi. I also refered to striver's website but smjh hi ni aara kuch. Should I leave it for now ? (ps- I am a beginner first year student)
@@crazybro4383 just keep working you will eventually understand.
You are like Virat Kholi.
Consistent and hardworking
Yes...
Better than kohli
kohli can't secure 1000 students' future but striver can.
Don't compare a great teacher with a choker
@@arnab027 yeah but kohli do donate money to save lives of lakhs of people and he also made our country pride a large number of times you fools
Outstanding Explaination...
I cant able to understand by watching this video even 2 times. It doesnt mean, striver didn't explained well.
He explained very well.
so, people who are not able to understand it well, try to watch it again and again...!
Dont search for other videos for this question, and if you even search, I will assure you that, you cant able to find better explaination than this..!
Striver, Thank you so much...!
Absolutely brilliant. Haven't seen anyone else on RUclips explaining any dsa problem with this much clarity.
Understood !! Both Interviewer And Me Are Super - Duper Impressed !!
This man is a god straight from heaven for programmers. The Clarity he has in his explanation is absolutely Amazing! Never seen a guy who is so passionate teaching DSA. Love you Raj Bhai! ❤
#Free Education For All.. # Bhishma Pitamah of DSA...You could have earned in lacs by putting it as paid couses on udamey or any other elaerning portals, but you decided to make it free...it requires a greate sacrifice and a feeling of giving back to community, there might be very few peope in world who does this...."विद्या का दान ही सर्वोत्तम दान होता है" Hats Off to you man, Salute from 10+ yrs exp guy from BLR, India....
The best video till now I have seen for this problem . 41 minutes explanation for a single problem is just a next level thing.
You are doing a wonderful job man!!! Really grateful to people like you who provide such quality content with such a dedication !!
Amazing!!💗💗 Also, we can further trim down the code provided in 26:46. If we intialize our HashMap with map.put(0,-1), we can skip checking the condition of if(sum==k)
Took me 3-4 passes to finally get the thought process through my head. But UNDERSTOOD it finally :)
kya aadmi h yaar!! dedication amazing 😍
In bruteforce approach we can also add the condition to reduce the number of operations that if(sum >K)break from the inner loop if the array contains positive elements only
Teaching is an art and you have nailed it, my friend. Another amazing one from Striver. Thank you!
bahut time lag gaya samajhne mai but finally samajh aa hi gaya
18:17 I can't understood the brute solution using hashing. It goes beyond my head😂..
bruh try rewatchung the video
true i figure out the optimial solution before brute and better approach
same, and also hashing means use of hashMap right but where he used Hashmap ? please someone correct me if I am wrong
@@CodeWithMeee bro! map is also used for hashing .
@@nirbhaybhardwaj4330 yes, now i understand...I have no knowledge about that earlier. thanks
thank you so much striver for everything ,today i did this question on my own without watching video but only with my intution it took me around 3hrs but it felt so good and its all because of you. thanks a lot (raj sir)😇❤ @take U forward !!🔥🔥🔥🔥🔥🔥🔥
Bhai kha placement hui
Watching the video 2nd times, first time was yesterday and now things are getting little inside my head. Thnx Striver.
Really striver you are awesome lot of people who explain concepts but the way you explain the concepts its mind blowing .Really impressed with your teaching skills
It's a bit complex to learn this in the first go. Maybe it would require re-watching the same multiple times.
Yeah, I thought that was not my cup of tea but after watching it 2nd time, I got the approach!!
This is the lecture when I understand hashing properly.
Thanks striver👍
Raj, Thanks a lot for This Amazing Video about C++ Arrays
Video - 4 Completed ✅
Understood in one go. but had to pause a lot and dry run everything in pen paper. nice question!
This is called consistency❤❤
the one who comes up with this solution on his own must be a genius
Virat Kohli of Programming 🌟🗿
Hey did u get how k=3 in 1st eg then in last eg k=6
took me more than 5 attempts to understand the edge case 😵💫
This lecture is too good 😍🤩 and the Mentor , he obviously needs no introduction 💥
That OVERALL was crazy !😂😂
One of the best explanation for this type problem.
Need to see the video 3 times but at the end got it.
Finally understood the concept 😮💨
37:42 Understood ❤ dada .Thank You
That satisfying song at the end .I always wait till the end for that.😂😊❤
Starts at 0:50
Simpler and easy to understand code for 2 pointer approach (works for array with no negatives):
int longestSubarrayWithSumK(vector a, long long k) {
int n=a.size();
int left=0, right=0, mx=0;
long long sum=a[0];
while(rightk) //want to decrease the sum now
{
sum-=a[left];
left++;
}
else if(sum
I still don't understand how the optimal solution is coded.
- While explaining the thought process and dry run, the first step we did was to keep adding the a[p2] elements.Then if sum exceeds, remove a[p1]s.
- It's strange why these steps got reversed while coding. In the code, first we remove the a[p1]s and then kept on adding.
-A general thought is to follow the thought process/ dry run. Surprisingly, if we write the code following the thought process it'll fail. That was the mistake I've made.
-But, still I've understood. Thanks Striver!
You are my inspiration bhaiya ..
And I am really a big fan of you, blessing me to become like you.
WE can simplify moving to right is we just initilize the sum to zero:
int longestSubarrayWithSumK(vector nums, long long targetSum) {
int n = nums.size(); // Size of the array.
int left = 0, right = 0; // Two pointers.
long long currentSum = 0; // Initialize currentSum to 0.
int maxLength = 0;
while (right < n) {
currentSum += nums[right]; // Add the current element to the currentSum.
// If the current sum is greater than the target sum, reduce the subarray from the left
// until the current sum becomes less than the target sum.
while (left targetSum) {
currentSum -= nums[left];
left++;
}
// If the current sum is equal to the target sum, update the maxLength.
if (currentSum == targetSum) {
maxLength = max(maxLength, right - left + 1);
}
// Move the right pointer forward.
right++;
}
return maxLength;
}
thanks a lot
thank you
Exactly, prefix sum is not necessary here. I am assuming he is just trying to explain the concept but it's really not necessary as all the numbers are positives
if anyone wondering why cant we write else if(sum>K){ rem code}.. take this example nd dry run A = [-1, 2, 9, -7, 3, 4] and K = 7 you will get it.
While neetcode is good, I always come to this channel for better indepth explanation and intuition. And the dry runs are a plus
Making my DSA journey superb ❤ hats off to u
Understood! Amazing explanation as always, thank you very very much for your effort!!
i love this guy, he's like talking to you in person.
That much clarity and explanation 🔥🔥🔥
Watching Your Lecture on the night of 31st December.
I guess optimal approach edgecases and code in the video is tough to remember. I tried to code it with my thought process. Hope this helps other
public static int longestSubarrayWithSumK(int []a, long k) {
// Write your code here
int max = 0;
int left = 0;
int right = 0;
long runningSum = 0;
//Indicates wheter we are moving right pointer
boolean rightMove = true;
while(right k) {
runningSum -= a[left];
//since element at right is already added, marking this indicator as false
rightMove = false;
left++;
}else if (runningSum == k) {
max = Math.max(max, right-left + 1);
rightMove = true;
right++;
} else {
rightMove = true;
right++;
}
// if shift of left results in crossing right
if(left > right) {
right++;
rightMove = true;
}
}
return max;
}
wonderful you've taught both approaches together.
can someone explain me the part where we update the map by -- preSumMap[sum] = i;
In the first question, can we break the inner loop if the sum is greater than the required k because the loop only contains positive integers?
int longestSubarray(vectorarr, int k){
int maxLength = 0;
for(int i = 0; i < arr.size(); i++){
int sum = 0;
for(int j = i; j < arr.size(); j++){
sum += arr[j];
if(sum == k){
maxLength = max(maxLength, j-i+1);
}else if(sum > k){
break;
}
}
}return maxLength;
}
In case of the Optimal solution, if arr=[ 1,1,1,1,1,1,1] , k = 1
Then the left pointer will always move whenever the sum will be increased by right pointer. So I think in the worst the case Time Complexity of the optimal solution will be O(n^2) .
Please correct me if I'm wrong !
@takeUforward
You are right about the pointers moving in each iteration but the complexity is where you are wrong.. It would not be O(n^2) rather it would be O(2n) (n times the left pointer will move and n times the right pointer will move) and O(2n) is equivalent to tc of O(n).
n^2 tab hota agar har 1 right move ke lie left puri array traverse kr jata but in this case 1 right ke lie 1 left move hora hai har baar. left =n,right=1 =>0(n*1)
Worst Case would be - arr=[1,1,1,1,1,1,1,100], k=10
yahan pe right 7 baar move krega aur +100 hote hi sum>k ho jaega. sare left hatane par bhi sum
You made DSA very interesting😄
Amazing quality, Cant thank you enough. top notch explanation, and nobody teaches DSA in this depth from my learning experience. i dont have words to thank you, may god give you all good health , happiness and wealth to continue this noble cause,
This is life saving. Salute!
this series is really commendable. Learning a lot.
For those who are unable to understand, run this C++ code or ask GPT to convert the C++ code to the language you are using
c++ code -
```
#include
using namespace std;
int getLongestSubarray(vector& a, long long k) {
int n = a.size(); // size of the array
map preSumMap;
long long sum = 0;
int maxLen = 0;
for (int i = 0; i < n; i++) {
// Calculate the prefix sum till index i
cout
bro but how will define values of presummap
@@jillavishwas35
If `rem` (which is `sum - k`) exists in `preSumMap`, we check the subarray length (`i - preSumMap[rem]`).
If this length is greater than `maxLen`, we update `maxLen`.
If `sum` isn't already in `preSumMap`, we add it with `preSumMap[sum] = i;`, meaning that `preSumMap[sum]` records the first index where the cumulative total equals `sum`.
If you're still confused, think of it this way, for each unique sum we encounter, we store the earliest index `i` at which this sum occurs, where `preSumMap[sum]` keeps track of the cumulative sum up to that index.
strive for excellence ❌ Striver for excellence✅
awesome explanation, i will watch it again and then solve to understand it completely.
for positive K value, the optimal solution does not work for test case Arr = {2 , 5 , 15, 16, 2 , 0, -5 , 2} and K = 15.
The answer should be 5 but it gives 1.
Absolutely Brilliant Explanation !! You explained the problem with so much clarity.
This has gone completely over my head 😬😬
Indeed Was really overwhelming, I think gotta keep going and someday gonna come again to this question with better confidence and with more no. Of questions, specially for the hashing approach.
Really power packed video 🥲
Understood and Implemented too !!
Could you explain to me? For positives and negatives problem?
Awesome sir.Kindly solve String problems as soon as faster.
It will be helpful for my placements.
I think first solution can ve done without taking 3d loop you juts take sum variable before j loop and use that and since it's positive numbers only you get out of j loop once it exceeds sum
genuinely one of the best cousrse man!!
OMG my first thought and my initial solution was literally the optimal solution and I didnt even realize it 🤦
not understand the better approach
and also little bit confuse in Optimal sol.
Watched it 3 times now to toally understand tho it's still a bit unclear but the explanation was really good hope I'll understand if I watch once more
0:00 intro
0:55 subarray
3:40 brute force
can you make vdos for web dev course ...your way of teaching is superb and interesting ..and i catch the topics quicking when you teach ...
sir the better part made me feel im under the water here too much raining .....................uwuwuwuwuwuwuwu......overall brute and optimal is understood
radha rani apko boht ashirvaad de sir ❤🙏🙏
Amazing intuition as always!!!!
But striver consider the following input:
6 15
-13 0 6 15 16 2
where array size is : 6
sum to be found: 15
the optimal solution is giving output: 0
But the output should be: 1 right.
optimal answer is only for positive integers, he says in the video that the better answer cant to optimize any further.
brilliant 2 pointer explanation
Understood Bhaiya ❤❤
crystal clear and to be point explanation..!
If you explain the code line by line it will be easier to understand
Heyy Striver, Can we use the variable-sized sliding window approach for this question ??
But when did we store the sum of the array elements in the map .??
Please anyone help me , how do you store the sum of the elements of array into the map with their indexes?
but your better solution is returning the maxlen value=1, but it shuold 3 please anyone explain me
had to watch a couple of times but good
Aaaaand this is an easy level problem. Shows how the hardness level is often mislabelled.
Best Explanation Ever
This problem was tough for me fr. But i tried understanding it b taking notes and doing a dry run by myself, and watching the video for a 2nd time and finally i understood. Thanks bhaiya this really boosted my confidence. I am still a noob in dsa but gradually i can come up with optimal logic and this is boosting my confidence.
hey can u tell me what does this line do
if(preSumMap.find(rem) != preSumMap.end()); i am not able to understand how this work and what is it checking
@@saahityabansal1254 ye map me remaining ko dhundega and agar use nahi milta to wo end pe phuch jata hai so wo loop me nahi jaega but agar use miljata hai that means it won't go till the end and like 4th,5th position pe ya khi par bhi milgya that will be it's answer and not the end so wo end ke equal nahi hoga jiska mtlb if statement true ho jaegi and wo andar enter kar jaega. i know thodi confusing si explanation hai but hai confusing kya hi kre ek do baar dimaag lgakar padho smjh jaoge
11:00 - Hashing approach solution Better approach
can we apply the kadanes algo here
what a crystal clear explaination, understood!
Understood
Thank you Striver
Hello Striver & Community,
At 25:52, one edge case failed not because of Time complexity.
My Java Code which has passed all the test cases:
public static int longestSubarrayWithSumK(int []a, long k) {
int n = a.length;
int res = -1 ;
HashMap prevSum = new HashMap();
long sum = 0 ;
for(int i =0; i
It has failed because of one more minor edge case.
n=37 k=52
0 2 5 3 3 4 4 3 0 5 5 4 4 4 3 2 0 2 3 1 3 0 4 3 1 4 5 2 4 3 1 4 5 0 3 4 0
Expected Output :
21
But we'll get 20
Can u pls explain the case [2 0 0 0 3] if k=2