Largest rectangle in Histogram | Leetcode #84

This lecture explains a very popular programming interview question which is to find the largest rectangle in histogram.Given an array representing heights of each bar in a histogram, we are required to find the area of the largest rectangle which can be formed from the given histogram.I have first explained the problem using some insightful examples and then i have shown the most important observation for this problem.Using this observation, I have shown an algorithm with optimization using stack which can find the largest rectangle area in the histogram in just O(N) time using just 3 traversals.I have also shown the dry run of the code along with code explanation at the end of the video.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
Join this channel to get access to perks:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithTECHDOSE
TELEGRAM Group LINK: t.me/joinchat/SRVOIxWR4sRIVv5...
=======================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
USEFUL LINKS:-
Implement min stack: • Implement min stack | ...
Implement stack using heap or priority queue: • Implement stack using ...

[@venuvenu2719]

Best explanation on KZbin, many people simply showed the code instead of explaining the logic.

[@techdose4u]

Thanks man :)

[@punnarahul90]

Yes agreed neetcode and techdose are two beautiful channel

[@sharpshooter5931]

Bro do u have code of this problem?? In C longuage

[@devplus7131]

**Similar Questions, Monotonic Stack** 239. Sliding Window Maximum 496. Next Greater Element I 739. Daily Temperatures 862. Shortest Subarray with Sum at Least K 901. Online Stock Span 907. Sum of Subarray Minimums 687. Delivering Boxes from Storage to Ports

[@tanyarajhans7533]

Thank you!

[@letsdoeverythinginoneweek9398]

trapping rain water is mostly similar also

[@contactdi8426]

Thanks Buddy :)

[@rohitshirur7640]

thank you :)

[@zaidshaikh2536]

85. Maximal Rectangle

[@MadForCs16]

If I ever get selected in a Tier - 1 company. This channel would be having a big contribution to that.

[@techdose4u]

Means a lot ❤️ I wish you do

[@jrajesh11]

Best explanation on even why brute force works which no other channel was able to visually explain so well. Brilliant job keep doing more such videos for hard problems!

[@techdose4u]

Thanks :)

[@pruthviraj8071]

This is definitely the best explanation i could find on the internet. This guy showed how to solve it instead of just showing problem solution.

[@techdose4u]

😅

[@alessandrocamillo4939]

Of 4 videos I watched about this problem, this is the best. It describes the problem, builds up the required intuition and shows a real chain of thoughts that from the brute force approach leads to the optimal solution. Congratulation. Great job!!

[@techdose4u]

Thanks :)

[@KushalBhatia]

I think no one else can explain better than you. Problem was very overwhelming in the begining but at the end of 27th min I felt how patiently and clamly you made it clear with making my head hurt :) Keep making similar video. Really appreiciate your hard work

[@techdose4u]

Thanks :)

[@ayushupadhyaya7656]

It was hard to find video which explains the intuition behind the solution to this problem. And this channel always gets it right.Very good work. Btw, the max area calculation can be done when calculating the right limit array for each bar, so we need 2n traversals only.

[@techdose4u]

🤗 Right

[@hakoHiyo271]

I love how you walk through each and every step, which helps to sink in the algorithm and helps to clarify things I misunderstood or missed. Keep up with the good work!

[@snehabaser3155]

The way u explain step by step and reaching from brute force to optimal is awesome !!✨ Thanks ♥️

[@techdose4u]

Welcome :)

[@DevMaster947]

I watched other channels for the same question but couldn't not understand clearly. But this is best explanation video for this question. Best part is the you start with brute force approach which is more important than directly moving to optimal one.

[@techdose4u]

😊

[@souravkumar-ue8uj]

Your videos have helped me to a great extent. Recently I got placed at Barco systems as Software Engineer.

[@techdose4u]

Wow great ❤️ Congratulations 🎉

[@mohamedantar1249]

I just wanna thank you, because this is the best explanation on the planet for this problem.

[@danny65769]

Brilliant. Love the appoach of going from brute force to optimal. Love the step-by-step explanation and running through of the algorithm.

[@SairamDasari2000]

Top notch explanation i just coded it myself after your explanation, keep doing the good work.

[@gurubalaji5611]

Saying from my down to heart it is the best explanation in youtube for this problem..Hope tech dose and Take you forward alone enough to getting placed in faang like companies..

[@dayanandraut5660]

I was struggling with this problem for a quite long time because I was not able to understand the intuition behind it. Thanks to techdose for clear explanation of the intuition

[@techdose4u]

👌🏼

[@pratikjain3323]

Life savour, for beginners like me. Thanks so much!

[@Ajaykumar-pv5lp]

best explanation with all given logic I did not understand this problem solution with paid course but Because of you sir I understood thank you so much

[@techdose4u]

Welcome 😊

[@mazharuddin3647]

Phenomenal stuff. You can explain really well. Thanks.

[@KChen-ks4le]

I have tp say this is the best explanation among all the posts! Thank you so much for sharing!

[@techdose4u]

Welcome :)

[@jatinmittal9184]

Great explanation no one like u on KZbin , you achieve one subscriber Great work man

[@naveenmurali3972]

probably my first comment to a youtube video ! Keen and neat explanation for this problem .Thanks a lot

[@techdose4u]

Thanks :)

[@sakibshahon]

Very well explanation , Thanks a lot it helped me a lot. Specially liked the fact that even the brute force was explained.

[@krishnananddubey2870]

Thanks a lot sir 🙇🙏. Best vedio I have found on KZbin on this topic. You explained each and every bit of problem clearly. Thanks again.

[@techdose4u]

Welcome

[@harpercfc_]

This is phenomenal. Couldn't find a better explanation than yours.

[@aasthagautam9480]

best explanation i can find on the internet for this question.

[@borhansgallery5190]

So much clear explaination. Thank you very much :)

[@tanzimchowdhury320]

Amazing, just amazing, after 4/5 videos, this is the only guy that makes sense!

[@techdose4u]

thanks :)

[@vishalcelestine8654]

Thank you so much for such a clear explanation !

[@JC-hj3sn]

How do you only have so little subscribers and views? You're doing an amazing job with these explanations

[@techdose4u]

Thanks 😊 Share in your contact 😜

[@pamupravallika2391]

The best channel in KZbin thankyou techdose

[@sudhanshuverma1987]

Thanks for detailed explanation. Keep up good work.

[@chaitanya14499]

thank you soo much bro; you earned yourself a lifetime subscriber :)

[@suryansh70]

very nice and swift explaination keep up the good work👍👍

[@saicharan4669]

This is the perfect explanation , I have ever heard of , Hats off ! sir

[@techdose4u]

Thanks 😊

[@rejetimeghavardhan7805]

tanks a ton for such good explanation

[@adityaagarwal7291]

the explanation is just the best!

[@bepracticalweb]

best explanation on whole yt

[@callmedanioo]

Very helpful video!

[@helpingUgrow]

No one explains it better :) Thank you

[@techdose4u]

Welcome :)

[@ronit-22]

Best explanation !

[@ADNANAHMED-eo5xx]

Thank U so much man, plz dont stop making videos if u ever think views are less

[@techdose4u]

Welcome :)

[@anuragkhard]

Best Explainatin ever👍

[@meditationmusic9997]

Superb explaination 👍

[@ferozmohammad5841]

thanks for the tutorial, so helpful!!

[@Suraj6642]

this channel is better than (All the combined paid edtech), thank you very much

[@techdose4u]

Welcome :)

[@avikmallick2493]

your explanations are better than 20k rs paid courses' teachers.Thanks a lot

[@23butlouder47]

very good explanation

[@NiteshSingh5375]

nice explanation brother...

[@akashkp9013]

But popping from stack might need O(n) and traversal from left to right and right to left requires O(n), hence the total complexity should be O(n^2), right ?

[@balajijangde8470]

great explanation

[@jansiranis4480]

Thank you for explaining it very well. Can you tell if there is any dynamic programming involved here?

[@legitarrra3845]

You saved my life with this video, thank you very much :D

[@techdose4u]

Great ❤️

[@AbhishekThakur-gz6ul]

Best Explanation ever on the YourTube.

[@techdose4u]

Thanks :)

[@dataman4503]

People are showing steps of algorithm without explaining anything.... This is a gem of video which clearly explains the 'why' of algorithm. great job. btw, I see another solution in Leetcode with one loop, is it similar to this one? I dont understand that one loop solution.

[@techdose4u]

No need to overkill a problem if you can solve in same time complexity :)

[@dataman4503]

@@techdose4u I understand that the time complexity is O(n)，but during interviews some idiot interviewers will ask a follow-up question like 'hey can you do this without traversing the loop twice?' 😂

[@pujabhardwaj7569]

Great explanation sir.... the ways you explain is pretty awesome... very helpful.. thank you for such a great tutorial

[@techdose4u]

Welcome 😀

[@Arjun69]

Brilliant! Great Explanation.

[@techdose4u]

Thanks :)

[@Aryan-fi2qf]

The best explanation on the internet.

[@techdose4u]

Thanks :)

[@rishabhkumar8115]

great explaination for every sticky points

[@techdose4u]

😊

[@ankitranjan88]

much more complicated...but much more easy to understand.......thank you

[@techdose4u]

Welcome :)

[@elliotho3015]

Thank you so much! Really helpful explanation :)

[@techdose4u]

Welcome :)

[@Ravin_raze]

great content

[@Push1781]

Question: in above problem adding one more element a[6] = 0.75 , it will never be able to go to proper left limit as index 0 is popped out. Can you please explain ?

[@krishnaprabeesh2415]

Good explanation

[@venkataraman7962]

thank you it was clear

[@zehuazhou3390]

Thank you! I thought I could use a monatonic queue but still could not figure it out. You explained it very clearly

[@techdose4u]

Welcome 😀

[@satyasuvartha8595]

Nice one

[@jigtbbbf]

Sooooo helpful, you have my THANKS!

[@techdose4u]

Welcome :)

[@TheKeyToMusicOfficial]

clear explanation

[@bvsrevanth6856]

I have watched many videos on this problem but couldn't understand anything . Best explanation on youtube !

[@techdose4u]

Thanks :)

[@Aayush28jun]

won't popping the stack with a while loop increase the complexity to something greater than O(N)?

[@kolhesatish]

Clear thank You

[@sulaimant5690]

An Intuitive explanation. Thanks.!

[@techdose4u]

Welcome :)

[@vivekswami2182]

Best Explanation !!

[@techdose4u]

Thanks:)

[@madmax2442]

Can you please tell how to intuitively prove the time complexity to be O(n) for this problem? Does pushing and popping not contribute to greater time complexity?

[@ferozmohammad5841]

pushing and popping in stacks takes time complexity O(1). And as we're traversing through the given array once, the complexity became O(n).

[@DenisIsidoro]

@@ferozmohammad5841 In order to build the stack, there's a "while" inside a "for". Shouldn't it be O(n^2)?

[@DenisIsidoro]

The worst-case scenario happens when the bars are strictly decreasing and it's O(n^2) IIUC

[@jayeshbhoi6844]

Finally in this channel i understood the solution. what about space complexity? i assume it's O(N). correct me if i am wrong.

[@thangnguyen8063]

Perfect explaination . Keep goinggggg

[@techdose4u]

Thanks

[@fax160]

Good video

[@satwikkhandelwal3722]

Superb explanation!! Cheers man!

[@techdose4u]

Thanks

[@santoshreddy3]

Which tools do you use?

[@Otnielush]

Thanks a lot for our videos

[@calebo.a.6270]

Please what annotation tool do you use?

[@techykush7192]

thanks a lot sir for such a amazing explanation

[@techdose4u]

Welcome

[@animeshjain4594]

Amazing Explaination

[@techdose4u]

Thanks 😊

[@stepanstulov9871]

How is this O(N) in the solution with the stack, when we're foreach-ing over all bars (O(N)) but then _internally_ also while-ing through the existing stack and popping (times another O(n))? Isn't this a straight O(N^2). They are clear nested loops to me.

[@samr6781]

Nested loops don't mean O(N^2). How many times the stack will be filled and popped? 2N at most! So, 2N for the inner while loop + N for the outer loop = 3N = O(N) time complexity.

[@laraibanwar1618]

Grt explanation

[@techdose4u]

Thanks :)

[@shrutigupta9319]

Awesome explaination🤗🤗 Bhaiya

[@techdose4u]

Thanks

[@laraibanwar1618]

Bro plz include manachers algorithm I have been suggesting tech dose to all of my friends juat bcz of the great content ... Good job

[@techdose4u]

It will come someday :)

[@adilsyed8369]

Great explanation. Thanks a lot.

[@techdose4u]

Welcome

[@SANDIPKUMAR-es7qh]

This is very nice video and explained the problem in more simply way. int hist[] = {1,4,9,5,7,2,10,3,5}; OutPut : 16 I tried to run this program using the same logic for the above array. But not able to understand why it's giving 16 as an output. I think it should be 10*3=30. Correct me if my understanding is wrong

[@shlomokon]

Great explanation but some of the slides have some pre-existing values which don't fit the current example. The presenter strikes out those unmatching values and writes the correct ones next to them. It would be easier to follow if there were no such pre-existing values from a different example.

[@bhargav1811]

I was asked this question in my interview of meditab ahmedabad company.

[@evilgamer578]

is there a soultion to this problem with single traversal ?

[@biswajeetpadhi5713]

Awsome explanation sir..

[@techdose4u]

Thanks ☺️

[@theghostwhowalk]

Amazing explanation!

[@techdose4u]

Thanks Aditya :)

[@AshishKumar-qk9rc]

It was so good.... Amazing man

[@techdose4u]

Thanks :)

[@ShivamGupta-cx3hy]

Thank you so much sir really helpful

[@techdose4u]

Welcome

[@animalbubble5937]

We can reduce on more traversal by doing max area in the second one itself

[@istvanszabo6875]

great job!

[@techdose4u]

Thanks