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

This video explains a very important programming interview problem which is based on dynamic programming.The problem is to find the maximal area of rectangle in a given binary matrix.In this problem, we are given a binary matrix and we are required to find the largest area of rectangle.I have explained the intuition for solving this problem by giving some examples and then I have shown diagramatically, how to solve this problem by using the same concept of dp as we used to solve the problem of finding the largest rectangle area in a histogram.I have given dry run idea and at the end of the video, I have also shown the code walkthrough.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: techdose.co.in...
USEFUL VIDEOS:-
Largest rectangle in Histogram: • Largest rectangle in H...
Maximal Square: • Maximal square | Dynam...
#dp #dpongrid #techdose

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

[@apbh]

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

[@adityaojha2701]

Thanks for both video!!

[@techdose4u]

Welcome :)

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

[@dr_920]

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

[@divyarya7122]

Thank you! you're life saver

[@techdose4u]

Welcome 😊

[@sameergirkar]

Great Explanation!! Thanks for the video.

[@techdose4u]

Welcome :)

[@lets_see_777]

best channel on youtube for these questions.

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

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

[@bchen1403]

Excellent visualization!!

[@prakharagarwal6237]

Nice Explanation! Thanks!

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

[@vinitraj6268]

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

[@jayvideos341]

Soo nice explanation

[@JohnWick-kh7ow]

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

[@chamoli552]

Brilliant Explaination sir🙏

[@anupam6045]

wonderful explanation

[@kumarc4853]

thank you for the dose :)

[@K_EC_AnuragKumarMishra]

Best explanation🤗

[@kanwarkajla]

u r great sir

[@techdose4u]

Thanks 😊

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

[@mondayemmanuel191]

Great explanation as usual.👌🏿

[@harshyadav5162]

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

[@altafmazhar7762]

yes same question

[@krishnaprabeesh2415]

Good 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?

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

[@thecyberexperts5612]

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.

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

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

[@iit_da_munda]

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

[@mohitsaran9193]

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

[@varunmanchanda3972]

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

[@techdose4u]

No

[@scchouhansanjay]

👏👏👏

[@PradeepKumar-eq7kj]

nice...

[@techdose4u]

Thanks

[@ankitjangir01]

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

[@techdose4u]

Sure

[@tanishgotti3659]

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

[@seelamrameshreddy702]

Please Explain and provide Java Solutions as well

[@techdose4u]

Will try for JAVA 😅

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

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

[@whysoserious-yj1ku]

How is this a dynamic programming solution?

[@subhamkadam5594]

Can someone explain line number 12 of code

[@mahipalsingh-yo4jt]

1st comment;)

[@techdose4u]

😀

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

[@sanjeetsingh4743]

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

[@varunappriyasekar902]

please zoom in the program

[@danieldouglas4006]

hi, what writing app do you use?

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