Hello striver!! I can't tell how much your series is helping me get prepared. I always used to shy away from DSA style interviews and so had to settle for low paying jobs. But your videos have given me some hope. Working through it steadily on day 14 now. I have a quick suggestion/recommendation if you don't mind. I noticed you have added some questions since the first version of the list. And I totally get that! You will re-evaluate if some additional questions are needed. My only request is if you can take one good pass at every section of your sheet and try adding questions that you think are absolute must do, but you have not included them in the list far. Doesn't matter if you ever intend to make videos on those Qs or not. It would benefit the folks preparing from your sheet do a wholistic prep. Other than that, I really don't think I'd add anything else. You're doing lords work here man! You certainly have a flare for teaching and you're fortunate enough to have realized it early on in life! Keep it up.
Great explanation, thanks a ton❤️ Also, when I watched this approach as the first ever solution to this problem(from other content makers' videos), it was a bit confusing because I couldn't get the intuition correctly. Getting to know all the solutions in the brute - better - optimal order made it so better to understand❤️
This is a brilliant solution. There are plenty of explanations available for this problem. But optimising an already optimal solution is something out of the box.
Awesome work bro, the best point about your videos is that not only you explain the approach very well but you also give those little insights about the question in the interview itself. Like here you straightaway told that only tell this approach if the interviewer asks explicitly. This will make people perform much better in the interview because they know what to do when!
The intuition behind this approach is that when we do the NSL (nearest smaller left) pass, we have the left boundary/limit of the elements in the stack (since stack is increasing order). Then for each index i, we are just figuring out what all elements in the stack, have the right boundary equals to i.
Great explanation, thanks a ton❤️ Also, when I watched this approach as the first ever solution to this problem(from other content makers' videos), it was a bit confusing because I couldn't get the intuition correctly. Getting to know all the solutions in the brute - better - optimal order made it so better to understand Great explanation, thanks a ton❤️ Also, when I watched this approach as the first ever solution to this problem(from other content makers' videos), it was a bit confusing because I couldn't get the intuition correctly. Getting to know all the solutions in the brute - better - optimal order made it so better to understand Great explanation, thanks a ton❤️ Also, when I watched this approach as the first ever solution to this problem(from other content makers' videos), it was a bit confusing because I couldn't get the intuition correctly. Getting to know all the solutions in the brute - better - optimal order made it so better to understand Great explanation, thanks a ton❤️ Also, when I watched this approach as the first ever solution to this problem(from other content makers' videos), it was a bit confusing because I couldn't get the intuition correctly. Getting to know all the solutions in the brute - better - optimal order made it so better to understand
Thanks a lot for this explaination! The code can me more sortened by putting -1 initially in the stack, so that we don't have to worry about stack being empty and calculating the width according to that.
This is one of the most difficult problem but sir u explanation is best as always and to all those future techies who are reading my comment i just wanna say "Ho jaiga yrr bas laga reh".
Kudos to your hard work! You are adding so much value to those struggling with DSA, I am very impressed by the way you explain the algorithms. Thank you so much, this helps me a lot!!
Thanks striver, this explanation(more so the previous one) helps understand why the code every where else is written to address the problem. Folks are started on the wrong foot by going directly to this solution and trying to reverse engineer the thought process, which makes the problem hard. The previous solution should be it and this one should be just to further optimize and not even be put forward as the original solution
Thank you Striver for the amazing explanataion, I was stuck thinking of the stack solution and finally I am able to think about the intuition as well as the optimal approach.
I'm very happy after watching these two videos completely, as the method/way of solving is really understandable & just like which is needed for any beginner. really loved it. thanks a lot for such videos.....❤❤❤
i am so sad that now videos frequency is so less. Many students like me were following the sheet and now we are kind of stuck, like where to check that we took the right approach or not. you explained the concepts very well acc to interview. Please do something about it if possible.
Just take half hour to understand , Super clear.. , Core idea is, we will calculate the area only for all stack smaller elements , if we found bigger we will pop it.
bahi kya admi ho tum bahiyaaa , kaha se karte ho itni reasearch salute to you yaaar , love you 🥰🥰. Shuruwat mein kuch samajh nahi ara tha , par jaise jaise dry run kiya apne har ek cheej , apki kahi hui copy m uthar di , har ek cheej jo apne boli , aur at last mene intuion tak likh diya apni copy m khudse ki kya chal raha hai. LET ME EXPLAIN WHAT IS HAPPENING: 1.) In the Better Approach we are computing the answer for every Index but we use certain kind of precomputation , right ? 2.) But we don't need to do such precomputation we , can calculate RS and LS on the go we we maintain the increasing order in Stack. 3.) Why? , whenever a CURRENT_ELEMENT is lesser than STACK_TOP it will be RS for the STACK_TOP ( kyuki CURRENT_ELEMENT , STACK__TOP ke obviousy RIGHT mein lie karega na , toh woh PEHELA chota element hogya ) and THE_BELOW_GUY ( i.e. STACK_TOP ke necche jo pada hai ) will be our LS , ( kyuki increasing order maintain kara hai na bhai ) 4.) hence while traversal all the elements which cannot be possible RS and LS for smaller guys are marked. and all the original smaller elements that are RS and LS for other guys are left out in the stack 😂. 5.) so processing these guys assuming the last index to be N itself , having the lowest possible value ( - infinity man lo ) will be marked and all our areas are calculated. 6.) KUDOS to the champion , thanks striver bahiya 🥰
is it possible to think a solution like this during an interview? The brute force solution was still very intuitive. I was able to get think the brute force solution only, the optimised version of brute force was also still not very intuitive. So how to get this kind of intuition if this solution was intuitive for someone?
Bhaiya, To calculate the right and left min ind i used but it will take S(N+N+N) for (int i = 0; i < n; i++) { while (!st.empty() && v[st.top()] >= v[i]) { right[i] = st.top(); st.pop(); } if (!st.empty()) { left[i] = st.top(); } st.push(i); }
At eighth line we have a condition in while loop that histo[ st .top() ] >= histo[i] My doubt is that why we are using equal to in this condition because for finding right smaller element histo[st.top()] should be strictly greater than histo[i] (histo[st.top()] > histo[ i ] ) Can anybody explain this??
That line is not the condition for finding the NGR, but it is the condition that eliminates the elements which cannot be the NGR (as we perform pop operation), since equal elements cannot be strictly greater we pop it out from the stack, so is the = used.
Why are we so sure that we will get answer only from finding widths of indexes 1,4,6 in the stack? I mean how do we know which passes to ignore and consider only these passes?
@takeUforward I want to ask one question regarding this intuition that suppose that we are currently at index 7 (consider the diagram shown at time stamp 3:30 ) then we will pop the item at index 6 and will find the area of it considering the element at index 7 as its next smaller element and element at index 4 as its previous smaller element. But if the element present at index 7 was not 3 but 6 then how this intuition works? I can't understand because in that case considering the element at index 7 as its next smaller element is not correct. Please help!
Bhaiya please Tree series le aao. 🥺 Companies has started visiting our campus. I'm damn sure after watching your tree series we'll have full confidence there too . 🙏🏽🙏🏽
Less complex code with same method :- long long getMaxArea(long long arr[], int n) { // Your code here stack st; st.push(0); long long area = 0; for(long long i = 1; i < n; i++) { if(arr[st.top()] < arr[i]) { st.push(i); } else { while(!st.empty() && arr[st.top()] >= arr[i]) { long long val = arr[st.top()]; st.pop(); long long left = st.empty() ? -1 : st.top(); long long right = i; area = max(area, (right - left - 1) * val); } st.push(i); } } long long right = n; while(!st.empty()) { long long val = arr[st.top()]; st.pop(); long long left = st.empty() ? -1 : st.top(); area = max(area, (right - left - 1) * val); } return area; }
This code won't work for input array as : 1,2,3,4,5 For this we again have to iterate through the whole stack and update res: long long getMaxArea(long long arr[], int n) { // Your code here stack st; long long res =0; for(int i=0;i=arr[i]){ long long height = arr[st.top()]; st.pop(); long long width; if(st.empty()) width=i; else width = i - st.top() - 1; res = max(res, height*width); } st.push(i); } while(!st.empty()){ long long height = arr[st.top()]; st.pop(); long long width; if(st.empty()) width = n; else width = n-st.top()-1; res = max(res, height*width); } return res; }
Please explain this code. I got this from ChatGPT, but it would be helpful if you make a video on it: // T.C: O(n) // S.C: O(n) int largestRectangleArea_chatGPT(vector& heights) { stack st; int n = heights.size(); int maxArea = 0; for(int i=0; i
Literally, I have watched so many Videos. But Today I finally understood this problem. Thank you for making this video.
U need to watch aditya verma's explanation
same
i mean there are many solutions, but how can you even think till there that line of thinking is EXCEPTIONAL HERE!
Hello striver!!
I can't tell how much your series is helping me get prepared. I always used to shy away from DSA style interviews and so had to settle for low paying jobs.
But your videos have given me some hope. Working through it steadily on day 14 now. I have a quick suggestion/recommendation if you don't mind.
I noticed you have added some questions since the first version of the list. And I totally get that! You will re-evaluate if some additional questions are needed. My only request is if you can take one good pass at every section of your sheet and try adding questions that you think are absolute must do, but you have not included them in the list far.
Doesn't matter if you ever intend to make videos on those Qs or not. It would benefit the folks preparing from your sheet do a wholistic prep.
Other than that, I really don't think I'd add anything else. You're doing lords work here man! You certainly have a flare for teaching and you're fortunate enough to have realized it early on in life! Keep it up.
Better than any other RUclipsrs.... amazing lecture
your the only person in youtube to teach this solution. Thank you Striver[live long]
Great explanation, thanks a ton❤️
Also, when I watched this approach as the first ever solution to this problem(from other content makers' videos), it was a bit confusing because I couldn't get the intuition correctly. Getting to know all the solutions in the brute - better - optimal order made it so better to understand❤️
Taking u forward :)
@@takeUforward Absolutely :)
This is a brilliant solution. There are plenty of explanations available for this problem. But optimising an already optimal solution is something out of the box.
Awesome work bro, the best point about your videos is that not only you explain the approach very well but you also give those little insights about the question in the interview itself. Like here you straightaway told that only tell this approach if the interviewer asks explicitly. This will make people perform much better in the interview because they know what to do when!
Kindly upload videos more frequently , we would love to learn a lot of things from you as internship season is nearing
The intuition behind this approach is that when we do the NSL (nearest smaller left) pass, we have the left boundary/limit of the elements in the stack (since stack is increasing order).
Then for each index i, we are just figuring out what all elements in the stack, have the right boundary equals to i.
Great explanation, thanks a ton❤️
Also, when I watched this approach as the first ever solution to this problem(from other content makers' videos), it was a bit confusing because I couldn't get the intuition correctly. Getting to know all the solutions in the brute - better - optimal order made it so better to understand
Great explanation, thanks a ton❤️
Also, when I watched this approach as the first ever solution to this problem(from other content makers' videos), it was a bit confusing because I couldn't get the intuition correctly. Getting to know all the solutions in the brute - better - optimal order made it so better to understand
Great explanation, thanks a ton❤️
Also, when I watched this approach as the first ever solution to this problem(from other content makers' videos), it was a bit confusing because I couldn't get the intuition correctly. Getting to know all the solutions in the brute - better - optimal order made it so better to understand
Great explanation, thanks a ton❤️
Also, when I watched this approach as the first ever solution to this problem(from other content makers' videos), it was a bit confusing because I couldn't get the intuition correctly. Getting to know all the solutions in the brute - better - optimal order made it so better to understand
Thanks a lot for this explaination!
The code can me more sortened by putting -1 initially in the stack, so that we don't have to worry about stack being empty and calculating the width according to that.
Honestly this is the best channel there is. Thank you so much Striver.
This is one of the most difficult problem but sir u explanation is best as always and to all those future techies who are reading my comment i just wanna say "Ho jaiga yrr bas laga reh".
Bhut bhut sukriya itna acha solution kea liye
Understand this difficult soln in easy way ... We have striver 👍🔥
Kudos to your hard work! You are adding so much value to those struggling with DSA, I am very impressed by the way you explain the algorithms. Thank you so much, this helps me a lot!!
Thanks striver, this explanation(more so the previous one) helps understand why the code every where else is written to address the problem. Folks are started on the wrong foot by going directly to this solution and trying to reverse engineer the thought process, which makes the problem hard. The previous solution should be it and this one should be just to further optimize and not even be put forward as the original solution
UNDERSTOOD.............Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
you always brings the new approach...after your explanation I have cleared my doubts....Thanks..and please upload further videos striver.
this video shows how good he is at algorithms ,Thanks sir for everything that you make for us
what is time and space complexity here
What an explanation. Your videos are one of the best on youtube, please keep uploading more of 'em.
Bhai kamal ka video bnaya h..kmal ka explain kra h.. aagh lga di guru
Watched many videos, but not able to understand this problem from an year, finally understood , thank you for making this video🔥🔥
Thank you Striver for the amazing explanataion, I was stuck thinking of the stack solution and finally I am able to think about the intuition as well as the optimal approach.
After doing multiple dry runs.. this seems too easy! Thank you Raj sir 🙏
I'm very happy after watching these two videos completely, as the method/way of solving is really understandable & just like which is needed for any beginner. really loved it.
thanks a lot for such videos.....❤❤❤
i am so sad that now videos frequency is so less. Many students like me were following the sheet and now we are kind of stuck, like where to check that we took the right approach or not. you explained the concepts very well acc to interview. Please do something about it if possible.
@Eren Jaeger i am also thinking the sane thing. Lets hope it's true. Then it would be a great gift for all of us.
Released tree series :)
where can i find the sheet?
Literally I have watched so many Videos.But Today i finally understood this problem 🔥🔥 .Thank u so much💯🤞😌
Just take half hour to understand , Super clear.. , Core idea is, we will calculate the area only for all stack smaller elements , if we found bigger we will pop it.
bahi kya admi ho tum bahiyaaa , kaha se karte ho itni reasearch salute to you yaaar , love you 🥰🥰. Shuruwat mein kuch samajh nahi ara tha , par jaise jaise dry run kiya apne har ek cheej , apki kahi hui copy m uthar di , har ek cheej jo apne boli , aur at last mene intuion tak likh diya apni copy m khudse ki kya chal raha hai.
LET ME EXPLAIN WHAT IS HAPPENING:
1.) In the Better Approach we are computing the answer for every Index but we use certain kind of precomputation , right ?
2.) But we don't need to do such precomputation we , can calculate RS and LS on the go we we maintain the increasing order in Stack.
3.) Why? , whenever a CURRENT_ELEMENT is lesser than STACK_TOP it will be RS for the STACK_TOP ( kyuki CURRENT_ELEMENT , STACK__TOP ke obviousy RIGHT mein lie karega na , toh woh PEHELA chota element hogya ) and THE_BELOW_GUY ( i.e. STACK_TOP ke necche jo pada hai ) will be our LS , ( kyuki increasing order maintain kara hai na bhai )
4.) hence while traversal all the elements which cannot be possible RS and LS for smaller guys are marked. and all the original smaller elements that are RS and LS for other guys are left out in the stack 😂.
5.) so processing these guys assuming the last index to be N itself , having the lowest possible value ( - infinity man lo ) will be marked and all our areas are calculated.
6.) KUDOS to the champion , thanks striver bahiya 🥰
Bhaiya your method of teaching is very very good. :)
Crystal Clear Approach..Thank you very much.
Your explaination level is just incredible.... Waiting for tree series to come up
i feel so lucky i found this video, i love you man
Yahi toh dhoondh raha tha bhaiyaa!!!!thanku so much
Thankyou striver for making DSA so easy
its not just the intution but you also need skills to code the whole solution
awesome work sir , fan of you
bro your explanation is so good.
This approach is better optimized than previous one (part-1) but it is taking more time to execute than previous one (in Leetcode).
Leetcode runtime is a scam
🤧
the best explanation for this problem thanks.
best explanation of this method...
Understood! Thank you so much for your explanation!!
Thank You !!
is it possible to think a solution like this during an interview? The brute force solution was still very intuitive. I was able to get think the brute force solution only, the optimised version of brute force was also still not very intuitive. So how to get this kind of intuition if this solution was intuitive for someone?
Very Very good explanation
Hats off!!! What an explanation
Bhaiya very helpful as always, just improve voice quality a bit ❤️❤️👍👍
Thank you so so so much striver
the best one on youtube
always a gem
Best teacher 💙
Great explaination!!
baap of all solutions ,this one😀😀😀😀
tq for uploading such gud content :)
Bhaiya,
To calculate the right and left min ind i used but it will take S(N+N+N)
for (int i = 0; i < n; i++)
{
while (!st.empty() && v[st.top()] >= v[i])
{
right[i] = st.top();
st.pop();
}
if (!st.empty())
{
left[i] = st.top();
}
st.push(i);
}
Thank you.
At eighth line we have a condition in while loop that histo[ st .top() ] >= histo[i]
My doubt is that why we are using equal to in this condition because for finding right smaller element histo[st.top()] should be strictly greater than histo[i] (histo[st.top()] > histo[ i ] )
Can anybody explain this??
That line is not the condition for finding the NGR, but it is the condition that eliminates the elements which cannot be the NGR (as we perform pop operation), since equal elements cannot be strictly greater we pop it out from the stack, so is the = used.
When there are consecutive duplicate frequencies I think both ">" and ">=" would still work. I would prefer ">" though.
Why are we so sure that we will get answer only from finding widths of indexes 1,4,6 in the stack? I mean how do we know which passes to ignore and consider only these passes?
Waiting for your tree series 🔥
THANK YOU SO MUCH
understoooooooooodddddddddddddddddddd btw from dp to here
Thank you Anna
@takeUforward
I want to ask one question regarding this intuition that suppose that we are currently at index 7 (consider the diagram shown at time stamp 3:30 ) then we will pop the item at index 6 and will find the area of it considering the element at index 7 as its next smaller element and element at index 4 as its previous smaller element. But if the element present at index 7 was not 3 but 6 then how this intuition works? I can't understand because in that case considering the element at index 7 as its next smaller element is not correct. Please help!
if you are still wondering i submitted it without equal to and it got AC
everyone observing his teaching
le me: o t shrt alag hyy baabaa
there is an O(1) space, O(n) time solution as well afaik.
Please increase the video frequency as placement season is approaching
thanks
Striver has gained this approach grinding cf not lc for sure!
Thanks sir for this video i was trying to understand the solution on leetcode but i could not understand their single pass code
Impressive
Bhaiya please Tree series le aao. 🥺 Companies has started visiting our campus. I'm damn sure after watching your tree series we'll have full confidence there too . 🙏🏽🙏🏽
You are in fourth year?
@@nikhilchaudhary9123 Yes
one small doubt, is the stack prefilled here because we dont push any indexes into the stack??
Just Amazing
understood!!
If duplicates elements are there, then also this approach will work?
Please complete the whole sheet bhaiya!!!
Understood sir
Superb
just thanks striver :)
Nice t-shirt
if stack contains let say by value: 1 2 2 now comes 1 so for 2 in stack rightsmaller is 1 but leftSmaller is not 2 (just below it) ?
Won't it fail?
Understood
Revisit
🎉❤
✨👍🏻
understood
width should be (RS-LS-1)
Less complex code with same method :-
long long getMaxArea(long long arr[], int n)
{
// Your code here
stack st;
st.push(0);
long long area = 0;
for(long long i = 1; i < n; i++) {
if(arr[st.top()] < arr[i]) {
st.push(i);
} else {
while(!st.empty() && arr[st.top()] >= arr[i]) {
long long val = arr[st.top()];
st.pop();
long long left = st.empty() ? -1 : st.top();
long long right = i;
area = max(area, (right - left - 1) * val);
}
st.push(i);
}
}
long long right = n;
while(!st.empty()) {
long long val = arr[st.top()];
st.pop();
long long left = st.empty() ? -1 : st.top();
area = max(area, (right - left - 1) * val);
}
return area;
}
y it was giving stack empty exception i cant understand can any one help me with this.
does not a while loop nested in for loop make it O(n^2) time complexity ? please explain that
It has been explained.
The while loop does not runs for o(n) time. It overall runs for N time
Bro can u plz say where to how to follow companies for off campuses for freshers?
6:00
why is it not right-left-1?
999L to 1K like :), thanks for ur video
This code won't work for input array as : 1,2,3,4,5
For this we again have to iterate through the whole stack and update res:
long long getMaxArea(long long arr[], int n)
{
// Your code here
stack st;
long long res =0;
for(int i=0;i=arr[i]){
long long height = arr[st.top()];
st.pop();
long long width;
if(st.empty()) width=i;
else width = i - st.top() - 1;
res = max(res, height*width);
}
st.push(i);
}
while(!st.empty()){
long long height = arr[st.top()];
st.pop();
long long width;
if(st.empty()) width = n;
else width = n-st.top()-1;
res = max(res, height*width);
}
return res;
}
@striver_79 next question of sde sheet can u upload
sh*t just got real!
Now this course is going very slow
I am waiting for dp
wtf was this solution.......not at all intuitive......not understood
Please explain this code. I got this from ChatGPT, but it would be helpful if you make a video on it:
// T.C: O(n)
// S.C: O(n)
int largestRectangleArea_chatGPT(vector& heights) {
stack st;
int n = heights.size();
int maxArea = 0;
for(int i=0; i
Bhai Hindi language m bhi bataao na plzzz
see there are many people who don't know hindi , so try to understand !
Pepcoding dekhlo bhai.
Bohot mast hai.
Aur ye wala bhai bhi mast padhta.
@@nishantchaddha2953 lekin unka code java m hota h
Everybody doesn't know hindi bro. English is the common language which everyone knows and can understand
client ko bhi ye hi bolega kya? 😂😂