Maximum area rectangle in a binary matrix | Leetcode #85 | Maximal rectangle

[@harpercfc_]

This is awesome. Tons of problem solvers told me that this one is similar to #84 but I didn't get any bit. Thank you sir now I know where the correlation is

[@mismis3153]

Having visuals like this makes it easy to understand. What I did was check the area of every rectangle that you can create from any point. Of course, it has some optimisations but it was still slower than most submissions.

[@apbh]

Best explanation! Very easy to follow and implement. THANK YOU!

[@lets_see_777]

best channel on youtube for these questions.

[@wonderInNoWhere]

Not sure what kinds of person gave thumb down. Thanks for the clear explanation.

[@anantsaxena5454]

was able to write the code on my own thankyou

[@adityaojha2701]

Thanks for both video!!

[@techdose4u]

Welcome :)

[@divyarya7122]

Thank you! you're life saver

[@techdose4u]

Welcome 😊

[@sameergirkar]

Great Explanation!! Thanks for the video.

[@techdose4u]

Welcome :)

[@allen724]

Thank you so much for these videos! I have learned a lot from your channel.

[@techdose4u]

Welcome :)

[@jashhinger442]

Great explanation sir. Thanku so much.

[@techdose4u]

Welcome :)

[@yitingg7942]

Second comment, I don't know what to say, just extremely grateful about the fact that you are there!!

[@techdose4u]

I am glad to see you in every video :)

[@yitingg7942]

@@techdose4u I am a big fan of yours and will always support your channel lol !

[@techdose4u]

😂 Thanks ❤️

[@yitingg7942]

@@techdose4u I am a little stuck to understand why that when it is 0, we just change the entire column to 0.

[@JohnWick-kh7ow]

Sir isme kaha dp lagi. Ye samajh nhi aaya. Ye to stack vala question ho gaya.

[@ShubhamKumar-fi1kp]

LeetCode Solution : class Solution { public: vector NSL(vector heights){ // Function to find indices of next smallest left element vector left; stack st; for(int i=0;i= heights[i]){ while(!st.empty() && st.top().first>=heights[i]) st.pop(); if(st.empty()) left.push_back(-1); else left.push_back(st.top().second); } st.push({heights[i],i}); } return left; } vector NSR(vector heights){ // Function to find indices of next smallest right element vector right; stack st; for(int i=heights.size()-1;i>=0;i--){ if(st.empty()) right.push_back(heights.size()); else if(!st.empty() && st.top().first=heights[i]){ while(!st.empty() && st.top().first>=heights[i]) st.pop(); if(st.empty()) right.push_back(heights.size()); else right.push_back(st.top().second); } st.push({heights[i],i}); } reverse(right.begin(),right.end()); return right; } int MAH(vector& heights) { //Function to find maximum area of histogram vector right; vector left; right = NSR(heights); left = NSL(heights); vector width; int mx = 0; for(int i=0;i

[@balakrishnanr648]

​ @TECH DOSE is it DP ??? Its just a STACKS based ques right?? just finding NSL Nearest Smaller to Left and NSR Nearest Smaller to Right??

[@bchen1403]

Excellent visualization!!

[@prakharagarwal6237]

Nice Explanation! Thanks!

[@harshyadav5162]

The code link in description contains the code for the Histogram problem....

[@altafmazhar7762]

yes same question

[@chamoli552]

Brilliant Explaination sir🙏

[@K_EC_AnuragKumarMishra]

Best explanation🤗

[@ADNANAHMED-eo5xx]

u took size r = matrix.size() (line 4 of code shown), but while u made same matrix but with integer numbers, u took size r+1 (line 9 of code). Why?

[@vinitraj6268]

One more thing we can add the elements till we get 1 from upper rows, in order to make histogram

[@blasttrash]

How did you know that you can use "largest rectangle area in the histogram"? I mean how did you come up with this thought process? How to derive this? Do you have some process or you just found it on some site like gfg or leetcode or some textbook?

[@techdose4u]

You have to understand the logic for why Largest rectangle algo works. If you couldn't get it in the first go then please refer solution. It's appreciated to learn new observations and techniques rather than coming up with something new yourself everytime :)

[@blasttrash]

@@techdose4u but amongst 1000s of questions, how do you remember that histogram question? It was a coincidence that you did that question before this. But what happens if you face this question in interview first before every hearing about histogram question?

[@shivverma1459]

@@blasttrash well that is why interviews need a lot of practise beforehand.

[@blasttrash]

@@shivverma1459 essentially interviewing now has become memorization of "patterns" which is why as you said we need a lot of practice beforehand. If I was a scientist and coming up with new algorithm, I would have to read a lot of literature, run many experiments and analyze a lot of trade offs over a long period of time to come up with some of these algorithms. But to do so in a interview under the pretext of "problem solving" is just not possible. There is a hidden assumption laid by companies that they don't want problem solving skills, they want "hard work" and "memorization of patterns". essentially they are looking for skills of perseverance(since we would be spending a lot of time practicing things that might be boring or not that useful in grand scheme of things). And these are the skills that you need in corporate while building some useless features for certain products too.

[@it-137shubhpratapsingh4]

@@blasttrash hey does this mean, if I do more and more problems and keep revising them so that I know more new approaches it would be better than doing fewer problems on my own, like giving proper thought to the questions and trying to come up with a solution on my own.

[@jayvideos341]

Soo nice explanation

[@varunmanchanda3972]

Sir, I have one question. Can we do it using Recursion?

[@techdose4u]

No

[@girikgarg1268]

What was the intuition behind converting row of matrix to histogram?

[@sainikhil956]

Bro, watch the previous video in this playlist u'll get it for sure that is prerequisite! in that video we have to find maximum area of rectangle in 1D array in this video we have to find maximum are of rectangle in 2D array

[@wepafitness5612]

Does this code convert the Binary Matrix into a Histogram? I don't see how it's doing that. No biggie I can add that on my own, just curious. Thanks for the explanation.

[@anupam6045]

wonderful explanation

[@kanwarkajla]

u r great sir

[@techdose4u]

Thanks 😊

[@mondayemmanuel191]

Great explanation as usual.👌🏿

[@mohitsaran9193]

What is the significance or purpose of leftbound and rightbound ??

[@nareshh74]

Hi Surya, Thanks for the video😀. Can you pls tell which observation made you see the problem as histogram. Thanks.

[@techdose4u]

First I was solving by finding area of largest rectangle ending at a cell (bottom right) corner but it was not working. After that some random trial and error methods and also I had solved this histogram problem which made life easier.

[@nareshh74]

@@techdose4u I too started it like the square problem. But unfortunately, I couldn't come up with the histogram perspective like you did. Needs more practice I guess ✌️.

[@techdose4u]

@@nareshh74 Practice helps a lot.

[@balakrishnanr648]

​@@techdose4u is it DP ??? Its just a STACKS based ques right??

[@krishnaprabeesh2415]

Good explanation

[@sainikhil956]

Sir, but how to come up with these kind of solutions in interview if we haven't seen this before?

[@Thepankaz1]

Thats where you are right, you dont.

[@snehasamuel7426]

I have a doubt wrt to this question. I coded this problem and for the test case 5, 4 = {1011, 1011, 0101, 1111, 0001}. The output according to the logic you explained and I coded is coming 8 but the actual answer is 5. Where am i going wrong ? can someone guide me pls?

[@ankitjangir01]

It would be better if you show the last code part zoomed in.

[@techdose4u]

Sure

[@kumarc4853]

thank you for the dose :)

[@tanishgotti3659]

Where are we using solutions of sub problems to get solution? Isn't this supposed to be DP...

[@whysoserious-yj1ku]

How is this a dynamic programming solution?

[@seelamrameshreddy702]

Please Explain and provide Java Solutions as well

[@techdose4u]

Will try for JAVA 😅

[@iit_da_munda]

How this is a DP problem...?? ... this is purely a stack problem.

[@animeshjain4594]

Can someone tell me what is wrong in this code- I didn't used stack I just applied the while loop until I find the next element smalller than the current element in filling the left and right array. class Solution { public int maximalRectangle(char[][] matrix) { int n = matrix.length; int maxArea = Integer.MIN_VALUE; int m = matrix[0].length; int[] arr = new int[m]; for(int i=0;i=arr[i]){ j--; } if(j=0;i--){ if(arr[i+1]>=arr[i]){ int j = i+1; while(j=arr[i]){ j++; } if(j>=n-1){ right[i] = n-1; }else{ right[i] = j-1; } }else{ right[i] = i; } } int maxArea = Integer.MIN_VALUE; for(int i=0;i

[@PradeepKumar-eq7kj]

nice...

[@techdose4u]

Thanks

[@subhamkadam5594]

Can someone explain line number 12 of code

[@mahipalsingh-yo4jt]

1st comment;)

[@techdose4u]

😀

[@scchouhansanjay]

👏👏👏

[@vivekptl296]

Is code language is javascript?

[@Gamerschoicetechy]

JS CODE if(matrix.length == 0 ) return 0; let finalmax = 0; let arrforhistogram = new Array(matrix[0].length).fill(0); for(let i=0; i= heights[i]){ stack.pop(); } right[i] = stack.length ==0 ? heights.length -1 : stack[stack.length -1] - 1; stack.push(i); } } for(let i=0 ; i

[@danieldouglas4006]

hi, what writing app do you use?

[@sanjeetsingh4743]

How is one supposed to come up with such a solution in 45 mins? 😅

[@varunappriyasekar902]

please zoom in the program