Largest Rectangle in Histogram | Part - 2 (6-7 lines of Code Approach)
HTML-код
- Опубликовано: 5 июл 2021
- Check our Website:
In case you are thinking to buy courses, please check below:
Link to get 20% additional Discount at Coding Ninjas: bit.ly/3wE5aHx
Code "takeuforward" for 15% off at GFG: practice.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------------------------------- SDE sheet: bit.ly/takeUforward_SDE
Pre-req: • Largest Rectangle in H...
Watch at 1.25x for better experience ..
---------------------------------------------------------------------------------------------------------------------------
Problem Link: leetcode.com/problems/largest...
C++/Java Code: takeuforward.org/data-structu...
---------------------------------------------------------------------------------------------------------------------------
✅Use coupon-code "STRIVER" for getting 10% on all subscriptions of Unacademy
✅Use coupon-code "TAKEUFORWARD" for getting 15% for all CN courses: aff.codingninjas.com/click?o=...
✅Use coupon-code "TAKEUFORWARD" for getting 10% for all GFG courses: bit.ly/tuf_gfgCourse
✅Please Please SUBSKRIIIBEEEEE the new channel: / @striver_79
---------------------------------------------------------------------------------------------------------------------------
Products that I use:
Best Mic in Affordable Range: amzn.to/3hiTr9p
Yeti mic: amzn.to/3dL4tDF
Boya mic: amzn.to/3h4ROgy
Logitech webcam: amzn.to/3h7d2KI
Cooling pad: amzn.to/3y46pi4
Wacom pad: amzn.to/3xacSIq
Ring light: amzn.to/3y7aaU1
Mic Arm Stand: amzn.to/3qzMuFa
Digitek Green light stand: amzn.to/2U7B3bI
Digitek Stand: amzn.to/363m7Oo
Tripod: amzn.to/35ZmbyT
Office chair: amzn.to/3qysu5Z
Ipad Air: amzn.to/3hjpiXx
Iphone 12: amzn.to/3AavyJV
Watch: amzn.to/3hn7w5A
Macbook Air: amzn.to/363lSTu
Macbook Pro: amzn.to/3qCczDr
Board: amzn.to/3x8GLIO
Mouse: amzn.to/360Asv1
---------------------------------------------------------------------------------------------------------------------------
✅Placement Series: • Let's give back to the...
✅Placement Series (Arrays, Sorting..): • C++ and Java |Brute-Be...
✅Hashing Playlist: • Two Sum Problem | Leet...
✅Greedy Playlist: • N meetings In One Room...
✅Recursion Playlist: • L8. Combination Sum | ...
✅Graph Playlist: • 3 MAJOR ANNOUNCEMENTS ...
✅Two Pointer Playlist: • 3 SUM | Brute | Better...
✅Binary Search Playlist: • Nth Root of a Number U...
✅LinkedList Playlist: • Reverse a Linked List ...
✅Advanced DS playlist: • Fenwick Tree Tutorial ...
✅Stack&Queue Playlist: • Implementation of Stac...
✅Greedy Algorithms: • N meetings In One Room...
---------------------------------------------------------------------------------------------------------------------------
If you appreciate the channel's work, you can join the family: bit.ly/joinFamily
✅Thumbnail Creator: / rikonakhuli
✅ Striver's Linkedin Profile: /
✅ Instagram: /
✅Connect with us: www.google.com/search?client=... (Use Link in Mobile only, if not works search "takeUforward" in telegram)..
##dsa #striver #leetcode
![Sean Rii, Karyon, Sharzkii - Taungule [My Love] (Official Music Video)](http://i.ytimg.com/vi/eJoMuypbSzQ/mqdefault.jpg)
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
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
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.
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 :)
your the only person in youtube to teach this solution. Thank you Striver[live long]
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.
What an explanation. Your videos are one of the best on youtube, please keep uploading more of 'em.
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.....❤❤❤
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 understandGreat 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 understandGreat 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 understandGreat 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
you always brings the new approach...after your explanation I have cleared my doubts....Thanks..and please upload further videos 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
Honestly this is the best channel there is. Thank you so much Striver.
Crystal Clear Approach..Thank you very much.
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💯🤞😌
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".
UNDERSTOOD.............Thank You So Much for this wonderful 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.
Your explaination level is just incredible.... Waiting for tree series to come up
Understood! Thank you so much for your explanation!!
Bhut bhut sukriya itna acha solution kea liye
Understand this difficult soln in easy way ... We have striver 👍🔥
i feel so lucky i found this video, i love you man
Hats off!!! What an explanation
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.
Watched many videos, but not able to understand this problem from an year, finally understood , thank you for making this video🔥🔥
the best explanation for this problem thanks.
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
After doing multiple dry runs.. this seems too easy! Thank you Raj sir 🙏
Yahi toh dhoondh raha tha bhaiyaa!!!!thanku so much
its not just the intution but you also need skills to code the whole solution
Bhaiya your method of teaching is very very good. :)
Bhai kamal ka video bnaya h..kmal ka explain kra h.. aagh lga di guru
best explanation of this method...
Great explaination!!
tq for uploading such gud content :)
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.
Thankyou striver for making DSA so easy
Best teacher 💙
bro your explanation is so good.
Thank you so so so much striver
Thank you Anna
always a gem
Thank You !!
the best one on youtube
awesome work sir , fan of you
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?
Bhaiya very helpful as always, just improve voice quality a bit ❤️❤️👍👍
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 🥰
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
🤧
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?
If duplicates elements are there, then also this approach will work?
Very Very good explanation
THANK YOU SO MUCH
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?
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.
When there are consecutive duplicate frequencies I think both ">" and ">=" would still work. I would prefer ">" though.
Just Amazing
one small doubt, is the stack prefilled here because we dont push any indexes into the stack??
Please increase the video frequency as placement season is approaching
Thanks sir for this video i was trying to understand the solution on leetcode but i could not understand their single pass code
understood!!
Impressive
@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
there is an O(1) space, O(n) time solution as well afaik.
Thank you.
y it was giving stack empty exception i cant understand can any one help me with this.
Striver has gained this approach grinding cf not lc for sure!
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?
Waiting for your tree series 🔥
baap of all solutions ,this one😀😀😀😀
Please complete the whole sheet bhaiya!!!
Superb
just thanks striver :)
Understood sir
everyone observing his teaching
le me: o t shrt alag hyy baabaa
why is it not right-left-1?
Understood
width should be (RS-LS-1)
understoooooooooodddddddddddddddddddd btw from dp to here
understood
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
✨👍🏻
Nice t-shirt
@striver_79 next question of sde sheet can u upload
6:00
999L to 1K like :), thanks for ur video
Now this course is going very slow
I am waiting for dp
sh*t just got real!
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;
}
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 me bnao bro ..
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? 😂😂
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;
}
wtf was this solution.......not at all intuitive......not understood
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 understandGreat 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 understandGreat 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 understandGreat 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