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/codewithT...
TELEGRAM Group LINK: t.me/joinchat/...
=======================================================================
CODE LINK: gist.github.co...
USEFUL LINKS:-
Implement min stack: • Implement min stack | ...
Implement stack using heap or priority queue: • Implement stack using ...

[@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

[@venuvenu2719]

Best explanation on TH-cam, 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

[@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

[@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]

😊

[@snehabaser3155]

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

[@techdose4u]

Welcome :)

[@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 🎉

[@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]

👌🏼

[@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 😊

[@mohamedantar1249]

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

[@SairamDasari2000]

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

[@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?' 😂

[@saicharan4669]

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

[@techdose4u]

Thanks 😊

[@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!

[@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 😜

[@KChen-ks4le]

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

[@techdose4u]

Welcome :)

[@tanzimchowdhury320]

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

[@techdose4u]

thanks :)

[@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..

[@danny65769]

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

[@ADNANAHMED-eo5xx]

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

[@techdose4u]

Welcome :)

[@harpercfc_]

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

[@krishnananddubey2870]

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

[@techdose4u]

Welcome

[@naveenmurali3972]

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

[@techdose4u]

Thanks :)

[@Suraj6642]

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

[@techdose4u]

Welcome :)

[@pamupravallika2391]

The best channel in TH-cam thankyou techdose

[@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.

[@bvsrevanth6856]

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

[@techdose4u]

Thanks :)

[@mazharuddin3647]

Phenomenal stuff. You can explain really well. Thanks.

[@mohammadmoaddi2268]

How do you know the explanation is amazing?
After watching the explanation (without looking at the code), you write the code and it passes from the first time.

[@techdose4u]

😀

[@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

[@helpingUgrow]

No one explains it better :) Thank you

[@techdose4u]

Welcome :)

[@webpracticals]

best explanation on whole yt

[@AbhishekThakur-gz6ul]

Best Explanation ever on the YourTube.

[@techdose4u]

Thanks :)

[@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 ?

[@avikmallick2493]

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

[@ankitranjan88]

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

[@techdose4u]

Welcome :)

[@venuvenu2719]

Here is Java soltuion :
public int largestRectangleArea(int[] heights) {
// clue is we have to include the bar completely in the maximum rectangle
// we have to calculate for each bar, the area with width to the left and width to the right
// width to the left will be the smaller bar index to the left of the current bar
// lly width to the right
// to optimize the time to calculate width , we use stack
// if no smaller to the left , then put 0


int left[]=new int[heights.length];
int right[]=new int[heights.length];

//stack to push indexes
Stack stk=new Stack();

for(int i=0;i= heights[i] )
{
//keep popping the elements till the smaller element is reached
stk.pop();
}
//if stack is empty no smaller element to the left
left[i]=stk.empty() ? 0 : stk.peek()+1;

stk.push(i);


}



}

//now empty the stack
while(! stk.empty())
stk.pop();


// lly for right

for(int i=heights.length-1; i>=0 ;i--)
{
if(stk.empty())
{
// that means no element to the left, put it as 0
right[i]=heights.length-1;
stk.push(i);


}
else
{


while(!stk.empty() && heights[stk.peek()] >= heights[i] )
{
//keep popping the elements till the smaller element is reached
stk.pop();
}
//if stack is empty no smaller element to the left
right[i]=stk.empty() ? heights.length -1 : stk.peek()-1;

stk.push(i);


}



}

int max_area=0;
for(int i=0;i

[@techdose4u]

Thanks for sharing 👍

[@aasthagautam9480]

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

[@rishabhkumar8115]

great explaination for every sticky points

[@techdose4u]

😊

[@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 😀

[@Aryan-fi2qf]

The best explanation on the internet.

[@techdose4u]

Thanks :)

[@anuragkhard]

Best Explainatin ever👍

[@vivekswami2182]

Best Explanation !!

[@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 :)

[@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

[@fax160]

Good video

[@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.

[@Aayush28jun]

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

[@shrutigupta9319]

Awesome explaination🤗🤗 Bhaiya

[@techdose4u]

Thanks

[@pratikjain3323]

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

[@neelmungra14]

So technically we can say this problem is a modification of trapping rain water problem, right?

[@komalbisht1979]

no,they are different

[@jatinmittal9184]

Great explanation
no one like u on TH-cam , you achieve one subscriber
Great work man

[@TheKeyToMusicOfficial]

i feel that the only way it is possible to answer 1 or 2 of this difficulty of question in a coding interview is to have already solved it before that day.

[@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 :)

[@legitarrra3845]

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

[@techdose4u]

Great ❤️

[@ankurtiwari5664]

i can't understand why time complexity is O(N) in case of stack , in worst scenario it should be O(N*2)

[@stepanstulov9871]

I had the same thoughts. It's a while loop inside of foreach loop.

[@chaitanya14499]

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

[@mayurkapadnis4265]

Excellent explanation 🙏🙏👍👍

[@techdose4u]

Thanks

[@mayurkapadnis4265]

@@techdose4u it was a hard level question but you made it very simple with step by explanation with dry run of example which is awesome, I've recommended this content to all my friends

[@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.

[@sakibshahon]

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

[@NiteshSingh5375]

nice explanation brother...

[@bhargav1811]

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

[@rudranilacharya5293]

i did this with pair but now i think i there is no need to use pairs, but i do suggest to use vectors instead of arrays
class Solution
{
public:
vector second(long long a[], int n)
{
vector v2;
stack s;
for(int i=n-1;i>=0;i--){
if(s.size()==0){
v2.push_back(n);
}
else if(s.top().first=a[i]){
s.pop();
}
if(s.size()==0){
v2.push_back(n);
}
else{
v2.push_back(s.top().second);
}
}
s.push({a[i],i});
}
reverse(v2.begin(),v2.end());
return v2;
}
vector first(long long a[], int n)
{
vector v1;
stack s;
for(int i=0;i

[@laraibanwar1618]

Grt explanation

[@techdose4u]

Thanks :)

[@23butlouder47]

very good explanation

[@suryansh70]

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

[@jansiranis4480]

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

[@animalbubble5937]

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

[@satyasuvartha8595]

Nice one

[@ronit-22]

Best explanation !

[@danghuynguyen8579]

Great explanation, can you please make a video for the problem 1504. Count Submatrices with all ones

[@techdose4u]

I will try

[@techdose4u]

I will try

[@MahirHasancse21]

In your code, the problem can be solved using 1 array by calculating the maximun area in the second for loop instead of assigning the value of right limit.

[@techdose4u]

Yes right. But it will make harder for some people to understand 😅

[@MahirHasancse21]

@@techdose4u But your explanation is way much better than anyone.

[@techdose4u]

Thanks. But I just keep in mind that if you are watching the video then probably you might have missed some concept and explaining from ground level makes understanding simple. Later you can build your own optimisations when you know basics. Because everyone has their own way of building :)

[@borhansgallery5190]

So much clear explaination. Thank you very much :)

[@balajijangde8470]

great explanation

[@krishnaprabeesh2415]

Good explanation

[@Pinguru]

you saved my life

[@techdose4u]

😂

[@callmedanioo]

Very helpful video!

[@sudhanshuverma1987]

Thanks for detailed explanation. Keep up good work.

[@elliotho3015]

Thank you so much! Really helpful explanation :)

[@techdose4u]

Welcome :)

[@satwiksharma4359]

best explanation ever......

[@techdose4u]

Thanks :)

[@rejetimeghavardhan7805]

tanks a ton for such good explanation

[@meditationmusic9997]

Superb explaination 👍

[@adityaagarwal7291]

the explanation is just the best!

[@Otnielush]

Thanks a lot for our videos

[@adithyakiransekar]

Great explanation. But how can someone come up with this approach in 30 min interview and also code it?

[@brijrajsinhgohil6576]

isn't it O(n^2) because there is loop in a loop for finding left and right bars??

[@stepanstulov9871]

Same question.

[@ShivamGupta-cx3hy]

Thank you so much sir
really helpful

[@techdose4u]

Welcome

[@TheKeyToMusicOfficial]

clear explanation

[@NikhilSharma-mv8hq]

Awesome explanation 👍🏻

[@techdose4u]

Thanks 😊

[@dochimekashiariri7610]

Why is the complexity o(n) for filling left and right array

[@techdose4u]

Co it's one traversal operation :)

[@hemantagarwal5095]

You very well explained how to do it, but you didn't explain why to do it & what should be the approach, how do u come up with the observation etc :(

[@techdose4u]

You need to practice these to get the intuition.

[@cgqqqq]

you are the best

[@techdose4u]

Thanks 😊

[@satwikkhandelwal3722]

Superb explanation!!
Cheers man!

[@techdose4u]

Thanks

[@animeshjain4594]

Amazing Explaination

[@techdose4u]

Thanks 😊

[@meditationmusic9997]

Keep it up