L12. Largest Rectangle in Histogram | Stack and Queue Playlist

[@rakshitbisht8885]

Closed the video three times in three days , was not able to understand the approach or you can say was scared of the optimal approach and skipped the whole question many time but didn't gave up Its day 4 and now i have understood everything. I am quite proud of myself ;-).

[@RIPNANI]

🎉

[@rohanmujumdar7265]

I struggled for at least 45 minutes to get the Brute Code done by myself. I thought that is the most optimal. I am amazed at how someone's thought process can go to such a huge extent. This is an absolute Genius of you Striver. Hats Off!!!!!

[@kamalakannanng4206]

The Explanation for the most optimal solution is just Amazing! #GOATOFDSA

[@aniboy0071]

When he said "pretty simple, isn't it"! Nahi bhaiiiii!

[@himage6540]

🥲

[@udaykirankorada1771]

It is.. Watch again with cool mind.. And a pen and paper..

[@RahulSah-gd6pj]

The Explanation for the most optimal solution is just Amazing! Thank you

[@adityakumar-ps2bu]

I saw this problem in 2019 first and tried to understand with multiple blogs and videos but couldn't understand. I understood it here. Thanks Striver

[@harshasshet6755]

finally after 5 days of stressing out on this problem undeerstood the concept , man this guy is genius and i am thankfull to you man😊

[@shubham5646]

🤣

[@sanketatmaram]

best mono stack explanation series with proper intuition, great work!

[@hiraljhaveri3830]

For next or previous smaller element, in the while loop (which pops out elements), the condition we use is ">=" (greater than or equal to). Here, in the single pass approach we are using ">" (strict greater than). There are implications with duplicate elements in the input (just for fun understanding): Consider the input is [2, 2, 2, 2]: Case 1: If we were to take ">" (strict greater than), the area computed for each index will be 8, 6, 4 and 2 respectively. The last 2 (index 3) will be popped first and it will have the previous 2 (index 2) sitting on top of the stack, giving it an area of 2 x (4 - 2 - 1) = 2. For the next element, it will be 2 x (4 - 1 - 1) = 4, and so on. Case 2: If we were to take ">=" (greater than or equal to), the area computed for be reversed, i.e. 2, 4, 6 and 8 respectively. The first element (index 0) will be popped first when looking at second element (index 1), giving out area = 2 x (1 - (-1) - 1) = 2. Then second element will be popped while looking at the third element, and so on. In either case, the intermediate area computations (with duplicate elements sitting next to each other) are incorrect, because ideally in above case one would expect the area of 8 for each of the element. However, the maximum area will appear with one of the element, so we do get correct answer.

[@rajatshukla2605]

Great observation! Had a problem related to duplicates. Though someone in the comments might have mentioned it, and there you were!

[@sivatejaysn]

Very great intution and optimal solution is out of the box thinking

[@kamalesh4904]

This problem is just beautiful Reminds me how beautiful algorithms are

[@OmCanpe]

Yes it is indeed!

[@Afiniciado]

you just spoke to my heart buddy!

[@utkarshpal9377]

Damn i solved this question myself just 4 minutes in the video , brute force and optimal , Thank you Striverrrr!! Keep growing man

[@YazhiniSelvakumar-g7p]

i cannot unsertand the intuition for optimal solution at first , after spending lot of time i got it thank u so much for u r videos😍

[@data-fi4hl]

Absolutely mind Blowing Approach

[@vikassharma4-yearb.tech.mi375]

amazing u r the best. I didn't even see the pseudo code just solved the problem

[@kareni7572]

Thanks for nse, pse approach before optimised ! Couldn't understand the optimised directly 😃 Best Explanation🎉✨

[@kushjain1986]

instead of another while loop you can also add -1 element to start and end of array and then proceed as same class Solution { public: int largestRectangleArea(vector& h) { h.insert(h.begin(),-1); h.push_back(-1); int n=h.size(); int maxi=-1; stack st; for(int i=0;ih[st.top()])st.push(i); else{ while(!st.empty() && h[st.top()]>h[i]){ int height=h[st.top()]; int pse=0; st.pop(); if(!st.empty())pse=st.top(); maxi=max(maxi,height*max(1,(i-pse-1))); } st.push(i); } } return maxi; } };

[@gugli28]

I just closed the video when I understood I have to find prev and next smaller element. But After I submitted I saw my Time and then I came back to discover that there is more to this ques !! I have solve this in one iteration !!

[@chiragaparadh1417]

Hands down the best explanation for this problem

[@iamnoob7593]

Dry run is crazy for optimal , Just amazing , Thank you.

[@amanpreetsinghbawa1600]

At first this problem appeared to be a lot intimidating but I gave time to the striver's Question description & bingo!! I cracked it to be a PSE & NSE problem, Striver🔥Thanks for building the intuition in prev lectures, guys who are coming to this video directly, plz plz first go to the next greater ele video

[@seffsef6301]

Broo!! Ek question tha as a begineer what can be the roadmap new question nhi ban rhe

[@YourCodeVerse]

after watching the optimal approach multiple times in couple of days i was unable to understand it but on 5th and 6th day i watched it again and got every single bit of it understood everything completely optimal approach dekh kr aur smjh kr maza aagaya sach mai....

[@pragatisrivastava8051]

Majedaar problem, din ki achi shuruwaad hui!!

[@DevilJim-p1s]

The optimal one is work of a genius ❤

[@princeakhil208]

Thanks for providing a brief explanation on this

[@AkshitChaudhary-vx8iw]

Solved previous 3 question at own just because of Striver : ) Thank you Raj Vikramaditya Sir aka Striver #GOATOFDSA

[@whimsicalkins5585]

Beautify explanation. I love your energy ❤❤

[@tusharbadewale1424]

Are you going to update these links in A2Z sheet ? These videos seems latest and better

[@SubhashB22CH036]

class Solution { public: int largestRectangleArea(vector& heights) { stack st; int maxArea = 0; int n = heights.size(); for(int i = 0; i < n; i++) { while(!st.empty() && heights[st.top()] > heights[i]) { int element = st.top(); st.pop(); int nse = i; int pse = st.empty() ? -1 : st.top(); maxArea = max(heights[element] * (nse - pse - 1), maxArea); } st.push(i); } while(!st.empty()) { int nse = n; int element = st.top(); st.pop(); int pse = st.empty() ? -1 : st.top(); maxArea = max(heights[element] * (nse - pse - 1), maxArea); } return maxArea; } };

[@Vikas-i8p7m]

Take it out na, why are you waiting? take it out!😂

[@gireeswar18]

This problem is beautiful. Beautiful things are dangerous, this is an example.

[@karppakavallisaravanan9686]

Amazing explanation for optimal solution

[@moksh7130]

You are unreal!

[@DEEPAK-q7u5h]

mind blown away #striver, after watching above algorithm. #GoatForAReason.

[@UtkarshWasHereBeforeYou]

this is Art

[@atulwadhwa192]

mind boggling 🤯

[@nayankhuman1043]

Hats off man :)

[@ITSuyashTiwari]

optimal to bahut tagda tha

[@ramub9942]

Thank you bhaiya ❤

[@pranavmisra5870]

great explanation.

[@stool-c4w]

Isn't the time complexity of the brute force solution is O(4 * n ^ 2) ??

[@TOI-700]

#understooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooood, tysm vro !!!!

[@no_1313]

I have an issue with the optimal approach. What if there is a value that is to be popped and the top value is equal to it? Suppose the given vector is 2 3 2 1, so 2 is pushed at i = 0, then 3 is pushed at i = 1, then 3 is popped and maxarea is calculated for i = 2, there nse is 2 and pse is 0, and 2 is pushed. But then, for i = 3, before 1 is pushed 2 is popped, there is nse is 3, it's fine. But pse is becoming 0 there because s.top() is still 2, but the same height can't be pse because it is added in the width. There is my issue. Instead of pse becoming -1, here pse becomes 0. Can someone plz explain?

[@TejasSameerDeshmukh]

You're correct. Let me try to explain. Its little intuitive. For the 3rd element, we indeed get a wrong answer. if you print the Areas at each iteration, you can verify it. Yet the overall answer comes out to be correct, because the case ignored by this 2, is covered by 1st 2. Think about it, when you're at i=0, the max width is 3 (0,1,2 positions), and the same is at i=2; so, even if this area is not covered at i=2, it will be covered by i=0, the original guy that arrived, as for it, the right is same as the right for i=2 i.e nse = 1 at posi 3. but for i=0, pse will be still -1, which may not have been covered by i=2, but this guy covers it. If you still don't get it, try printing areas.

[@no_1313]

@@TejasSameerDeshmukh Yup, what I previously understood was that if same element is considered in pse, it is giving wrong ans, but will be managed during the other element's nse. But, I just wanted to make sure my observation is correct.

[@navyagandham9019]

A small question in the brute force approach Are we storing value of next smaller element or the index of nse ? If we are storing value , then in the above example arr = 2 1 5 6 2 3 if we take element 6 , nse would be 2 and pse would be 5 then area of 6 i.e., 6*(2-5-1) would become negative , but the actual area of that bar is 6 * 1.

[@yourhonestbro217]

index

[@riteshhere8611]

WE SHOULD STROE THE INDEXES

[@hardikpatel352]

Thanks a lot

[@shleshgholap1346]

If you are able to understand the approach 2, just watch Neetcode's explanation for the same problem and then come back to striver's explanation. You will understand the problem clearly then.

[@Afiniciado]

"pretty simple, isn't it"! this line blew my mind🫨

[@oyeshxrme]

thanks bhaiya

[@AnandSharma-ei1fv]

UNDERSTOOOOD

[@ChaitanyaDugyani]

sir explain sum of or of all subarrays please

[@nagendramarisetti]

Hey striver, why we need to assign 'n' to nse not '-1'?

[@ValluriLahitha-nw1lt]

While calculating differences, Since we are playing with indices we should consider taking the size of an array instead of -1.

[@rushidesai2836]

Had to watch this twice to understand this.

[@bill-cipher000]

No way anyones coming up with the optimal approach in an interview, phew..

[@coading.h4037]

why we need -1 at (nse-pse-1) can someone explain?

[@yasaswinikarumuri9590]

15:02 why am I kicking them out🤭

[@KartikeyTT]

tysm sir

[@karmathefirst1945]

pretty simple !! 😅😅

[@DeadPoolx1712]

UNDERSTOOD;

[@praneetdutta439]

26:20 OHH HELL NAHH!!

[@data-fi4hl]

when the interviewer don't want to hire u

[@tanujasharma1262]

off topic but striver is so fine

[@dubon7157]

padh le

[@roopeshdevapatiroopesh8388]

Understood

[@zenmonk29]

fkin legend

[@data-fi4hl]

Aint no way we can come up with this approach in the interview

[@thenerdguy9985]

But now you can if you see a similar question, and it strikes that it requires a monotonic stack.

[@mdsajid7712]

Wrong answer 😢

[@shashank_0807]

Old video for Optimal Approach kzbin.info/www/bejne/oHTClIqCrpydias

[@dilshadazam880]

Wow you a beauty

[@vishwash-to8fo]

Anyone notice "wrong spelling of rectangle in thumbnail"😅

[@aanurraj]

[@sankargnanasekar8955]

public int largestRectangleArea(int[] heights){ Stack st = new Stack(); int maxRect = 0; int nse = 0; int pse = 0; int currElement = 0; for (int i = 0; i < heights.length; i++){ while(!st.isEmpty() && heights[st.peek()] > heights[i]){ nse = i; currElement = st.peek(); st.pop(); pse = st.isEmpty() ? -1 : st.peek(); maxRect = Math.max(maxRect,heights[currElement] * (nse - pse -1)); } st.push(i); } while(!st.isEmpty()){ nse = heights.length; currElement = st.peek(); st.pop(); pse = st.isEmpty() ? -1 : st.peek(); maxRect = Math.max(maxRect,heights[currElement] * (nse - pse - 1)); } return maxRect; }// Time Complexity: O(n) + O(n) = O(n) // Space Complexity: O(n)

[@AyushSingh-rx4iv]

Spelling mistake hai thumbnail me

[@OmCanpe]

True sdet found here, jaldi apply kro 😂

[@zaffarzeshan1308]

very bad

[@deepthibattala8886]

Can anyone help with my code. This is giving me wrong output. I have tried two approaches. Both are not giving output properly. import java.util.*; public class Practice { public static void main(String[] args) { Scanner sc = new Scanner(System.in); StringBuffer s = new StringBuffer(sc.next()); int n = sc.nextInt(); int[] a= new int[n]; for(int i=0;i a[i]) { int height = a[st.pop()]; int width = st.isEmpty() ? i : i - st.peek() - 1; area = Math.max(area, height * width); } st.push(i); } while( !st.isEmpty()) { int height = a[st.pop()]; int width = st.isEmpty() ? a.length : a.length- st.peek() -1; area = Math.max(area, (height * width)); } return area; } private static int largeRectangle(int[] a, int n) { List nse = new ArrayList(); List pse = new ArrayList(); nse = findNSE(a); pse = findPSE(a); int maxRec = 0; for(int i = 0;i=0 ;j--) { while(!st.isEmpty() && a[st.peek()] >= a[j]) st.pop(); nselis.add(st.isEmpty() ? a.length : st.peek()); st.push(j); } Collections.reverse(nselis); // Reverse the list to match the original order return nselis; } private static List findPSE(int[] a) { List pselis = new ArrayList(); Stack st = new Stack(); for(int j=0 ; j< a.length; j++) { while(!st.isEmpty() && a[st.peek()] > a[j]) st.pop(); pselis.add(st.isEmpty() ? -1 : st.peek()); st.push(j); } // No need of Reverse the list because you're already processing the array from left to right. return pselis; } }

[@PeeyushSharma-pc8fc]

how the hell you even think of solution like the optimal one crazy dude! respect for those who can do it🫡

[@shrishagrawal3170]

Mind got tricked, but also get back to it's original way upon listening his mind blowing approach. 🫡

[@amanasrani6405]

is it easy to think of the optimal solution for a coder doing dsa over months? 🥲

[@SibiRanganathL]

Understood

[@abhinavabhi3568]

Understood

[@fanofabdevillersandmathslo5960]

Understood