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]

🎉

[@kamalakannanng4206]

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

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

[@RahulSah-gd6pj]

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

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

[@sivatejaysn]

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

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

[@data-fi4hl]

Absolutely mind Blowing Approach

[@utkarshpal9377]

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

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

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

[@vikassharma4-yearb.tech.mi375]

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

[@Afiniciado]

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

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

[@pragatisrivastava8051]

Majedaar problem, din ki achi shuruwaad hui!!

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

[@karppakavallisaravanan9686]

Amazing explanation for optimal solution

[@whimsicalkins5585]

Beautify explanation. I love your energy ❤❤

[@DEEPAK-q7u5h]

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

[@ITSuyashTiwari]

optimal to bahut tagda tha

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

[@atulwadhwa192]

mind boggling 🤯

[@UtkarshWasHereBeforeYou]

this is Art

[@rushidesai2836]

Had to watch this twice to understand this.

[@pranavmisra5870]

great explanation.

[@moksh7130]

You are unreal!

[@Vikas-i8p7m]

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

[@ramub9942]

Thank you bhaiya ❤

[@oyeesharme]

thanks bhaiya

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

[@tanujasharma1262]

off topic but striver is so fine

[@dubon7157]

padh le

[@TOI-700]

#understooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooood, tysm vro !!!!

[@karmathefirst1945]

pretty simple !! 😅😅

[@tusharbadewale1424]

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

[@hardikpatel352]

Thanks a lot

[@DeadPoolx1712]

UNDERSTOOD;

[@data-fi4hl]

when the interviewer don't want to hire u

[@AnandSharma-ei1fv]

UNDERSTOOOOD

[@ChaitanyaDugyani]

sir explain sum of or of all subarrays please

[@KartikeyTT]

tysm sir

[@roopeshdevapatiroopesh8388]

Understood

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

[@yasaswinikarumuri9590]

15:02 why am I kicking them out🤭

[@shashank_0807]

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

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

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

[@zenmonk29]

fkin legend

[@aanurraj]

[@vishwash-to8fo]

Anyone notice "wrong spelling of rectangle in thumbnail"😅

[@dilshadazam880]

Wow you a beauty

[@coading.h4037]

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

[@pulse.7]

because then the gap would be too big?????

[@mdsajid7712]

Wrong answer 😢

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

[@amanasrani6405]

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

[@SibiRanganathL]

Understood