Maximum Size Rectangle of All 1's Dynamic Programming

Given a 2D matrix of 0s and 1s, find maximum size rectangle of all 1s in this matrix.
github.com/mis...
github.com/mis...

[@freethinker977]

2020 - still the best explanation IMHO

[@hitesh3859]

2021 - still the best explanation IMVHO

[@皓楠叶]

@@hitesh3859 2024 - still the best explanation IMVHO

[@sait5489]

getting things very easily by listening to ur lectures... thank u :-)

[@2LegHumanist]

Great explanation. I've been struggling with this one. All over the internet people just plonk their code down without explanation, but you explain it so simply.

[@nikostrongioglou9941]

What exactly did he explain? He has an algorithm and he is walking through the algorithm... Nothing more than that. No word on HOW he came up with the algorithm or what is the intuition behind this...

[@anushree3744]

@@nikostrongioglou9941 exactly. Nothing on thought process.

[@VladimirDjokic]

Great explanation! You should write a book "cracking the code interview"

[@nguyenhoanvule5755]

No bro! He should write the book "how to make the coding interview become a funny game". I feel really comfortable about his explain

[@kant.shashi]

Each row adds to values for histogram bars unless the cell value is 0 .. (i.e. bar is gone) and so at each row/level we check out maximum area under histogram (above the row)..which is the max rectangle.

[@anonymousmail9932]

Really best explanation

[@ShabnamKhan-cj4zc]

U are always saviour for any tough question. Thanks for such simple explanation.

[@enjili6062]

Only a trivial personal thought for why the "histogram" strategy works: a rectangle must have its bottom width land on a row. Here, we are simulating through all the rows for to get the bottom width to make the rectangle the maximum.

[@ok123ut]

an intuition to the approach would have been amazing. but great explanation!

[@ashishdukare1313]

Please can you explain why this approach is working? what is the intuition behind it?

[@ShinAkuma]

where were you all my life. Been struggling way too hard with this problem yet it's so simple.

[@dibyendusarkar6821]

What I like about you, is you save a lot of time, thanks man

[@karanpathak528]

Hello Tushar awesome explanation can you pls advice book/wiki for this algorithm.

[@curious_haldar]

Beautifully explained

[@manivannanrajah]

can we get an explanation on why this approach works?

[@hardikraj9469]

@@Bdjdiwhbkdk Thanks it really clear things up

[@saifurrahmanbhuiyan925]

thnaks a lot tushar . i almost learnt all dp algorithm u provided. plz carry on ur great effort. and provide us more tutorial . I have learnt dynamic programmong from ur tutorial . i am indebted to you

[@vaibhavchhabra800]

+Tushar Roy At time @5:44 u said that the Maximum Size Rectangle containing 1's is that (located at bottom down). How did u find that that is the box containing max 1's .Obv by luking at box v know that since max size is 8 and this box size is also 8 ,v can say that yes this box is the one , but how will a computer do it ? V know that the max size is 8, how to find the position of that box ?

[@vaibhavchhabra800]

+Tushar Roy Ok thnx

[@robertkasper9890]

How would you modify this algorithm to return all the coordinates of the largest rectangle, or a specific corner & the width and height?

[@adhishmalviya2408]

we need 3 things to get co-ordinates length breadth and lower left vertex: i think now you can find it anyways Im not going to type all of that

[@nguyenkien5558]

Thanks for short and clear explanation!

[@SaitejaPamulapati]

I think it can be solved in O(1) space complexity , if you use 1st row or 1st column instead of extra array . Since you have no further use of it

[@wozhendeaa]

I think that what you are proposing will still be 0(n), where n is the width of the original array.

[@karthikk5895]

Agree with Billy Yang. Also, finding the largest histogram function itself might take a space of O(col/rows).

[@prakritiinusa]

ya your explanations are simple , so easy to understand.. Thanks!!

[@samarthsharma9019]

why are we using histogram ?

[@contactdi8426]

@@samarthsharma9019 For that answer, you have to look at this problem: "Largest Rectangular area in Histogram"

[@mateuszlewicki7616]

+Tushar Roy You write this algorithm has O(rows * columns) complexity. This suggests that finding rectangle in histogram is solvable in O(1) - this feels very wrong.

[@mateuszlewicki7616]

sorry, You are right.

[@carsonliao8189]

Mateusz Lewicki I'm concerned about it too..

[@9351379627]

Hi Tushar, You explain every problem very well, but I dont understand why this histogram logic works here. Please explain..Thanks

[@sanyamsinghal7992]

for a rectangle we need two things, length and breadth, as the width is maintained by the array by summing up, then we just have to the appropriate length for given possible width so that we can decide our rectangle. So, with the help of histogram area here we are just deciding the best possible length we can have for a rectangle.

[@ameyapatil1139]

Looking at leetcode - Would temp[j]++ work instead of temp[j] += input[i][j]; on line 40 ?

[@DhanunjayG]

Hi Tushar..first of all thanks a lot for all your efforts..I have learnt a lot from you. Can we use and expand the same procedure above to find the largest subcube in a NxNxN cube cosisting of 1x1x1 subcubes with values either 0 or 1. like adding a new dimension to it. If possible can you please suggest the way forward

[@chaitanyadumpa2439]

Thank you Gautam gambhir

[@gyrogojo]

is this dynamic programming solution? We are not using solution to subproblems to get the final solution.

[@xxbighotshotxx]

Great question. Yes, we are. In order to solve for the input that we are given, we need to build the solution up row by row

[@imalive404]

@Exodus .. The histogram is formed taking into account the previous rows. The height of any bar in the histogram is dependent on the previous row . If you look closely if (i, j) == 0 then our histogram height there is 0. But if (i,j)==1 then histogram height is height(i-1, j) + 1. Formally Say, h(i, j) = height of histogram bar at i, j then if (i, j) == 1: ....h(i, j) = h(i-1, j) + 1 else: ...h(i, j) = 0 Hope this helps

[@jessematty8788]

nice video but how is an area of 5 a rectangle?

[@kartikkumar-6009]

hey it is not a dp approach so Y ur title include dp

[@ethantestimon9905]

Hi Tushar... I have one question: why the algorithm of maximum size square of all 1's will not work here?

[@deepanshugupta5299]

Every time I see his videos, I feel like its raining in the background

[@Neerajkumar-xl9kx]

or raining from ground hahahahahhah

[@arnavsingh0]

Although you explain things pretty easily but they are to be memorized if we go by your way.

[@mirnafayezboules3310]

Really you are amazing .. One of the best

[@seank9122]

so fast yet so clear. great explanation!

[@RaviMaurya-qi5ht]

Why can't I like these videos more than once!!

[@YashCodesX]

This is part of product design of 'KZbin'. Feel free to contact youtube devs

[@huynguyenquang1993]

Great explanation

[@CryingMG]

Lovely tutorials, Thanks alot Tushar! Learning so much from you!

[@sayeesh3236]

Good one Tushar!!!

[@varunsuryan1021]

You are a gem, mate.

[@aprofromuk]

@Tushar any idea how to compute the largest cross please?

[@ivanonyshchenko]

I am looking for explanation how to come to the described algorithm, but instead see what to do without explaining why

[@aishwaryabadgujar7532]

+Tushar Roy, this method works for all examples? Suppose the 5x5 2D matrix is 1 0 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 According to your method, the answer 4. Whereas the answer should be 6 (or 8 if you consider the vertical rectangle) Please help!

[@dhirajdwivedi3530]

ya this algo will work for all examples, for your example too for 1st row 1 0 0 0 1 max rectangle is 1 for 2nd row 0 1 1 1 0 max rectangle is 3 i.e. largest rectangle in histogram made by this array for 3rd row 1 2 2 2 0 max rectangle is 6 for 4th row 0 0 3 3 0 max rectangle is 6 for 5th row 1 1 4 4 0 max rectangle is 8 hence your answer i hope u got it 1 1 4 4 0 all indicates the height of histogram at each index of width 1 unit and u have to find the max area in each histogram and compare with the last one

[@aishwaryabadgujar7532]

Oh. For the third row, you do not consider that 1 while taking the max rectangle? If you take that 1, the max rectangle will be 4. So will have to apply some algorithm to choose the elements that form the max rectangle instead of considering all the non zero elements. Thanks for your help!

[@ShinAkuma]

You do consider that 1. He probably overlooked it. Row 3 = 00331. However this doesn't affect the maxArea. since max rectangle at this point will be: 111 111

[@SatyanarayanaBolenedi]

You Nicely build upon algorithm which u alrdy taught us!! Thanks Tushar!!

[@code_life4835]

what is the Intuition behind this working?

[@quirkyquester]

amazing explanation! Thank you!

[@7x34hj]

Do you have any videos Maximum Distance Matrices (MDS)? If not, could you do a quick one? Thx

[@singvijaya]

Could you explain how to calculate max histogram area without using the library function?

[@franciscov511]

Keeping the smallest of a continuous subset of non zero values

[@anubhavkumar1637]

You can calculate using stack

[@kkaabbccdd8080]

I would have really appreciated if you could have spent 1 min on code implementation at very high top level. +1 for your efforts on explanation.

[@dongreak4478]

how do you find the largest multiplication value in each row?

[@yernartalgatuly4252]

in which video did you discuss maximum size square in matrix?

[@yernartalgatuly4252]

***** thanks

[@wozhendeaa]

with the following case 100 010 110 if we use the largest rectangle method wouldn't his case result be 4?(2 in the first col and 2 in the second col)

[@wozhendeaa]

but the actual result is 2

[@brandonm1088]

1] 100 MAX is 1 2] 010 MAX is 1 3] 120 MAX is 2 When a row has a zero in it, it overrides the value in that slot, if that didn't happen then row three would have returned 220, which as we know is incorrect. Hope that helps, I don't think he explicitly mentions that behavior in the video, but it's there

[@mshyamkrishnan]

Is it possible to adapt this algorithm to find out biggests border with 1s ? (which means the inside of the subrectangle need not be 1) ? Great video btw!

[@shubham277]

Bro, in samsung they asked me this problem to find out biggests border with 1s and I could not make any progress.

[@guneettalwar2630]

Whats the intuition behind this?

[@torrtuganooh2484]

why do we add from the top in case of 1. Can anyone please explain?

[@gauravmamgain9225]

You are awesome. Your videos helped me a lot . Thanks man :)

[@j50313j50313]

Extremely helpful!

[@devendrasharma7999]

Thanks sir, this video made this question very easy .

[@javawicode]

how to solve problem when we want found maximum rectangle with- all of 0s

[@avinashkumar805]

convert 0 to 1 and 1 to 0 in the array and then do the same process on the new matrix.

[@jatinkumar4410]

nice explanation

[@sheetalshireen]

Hi Tushar...Thanks for helpful video..1 query - how to handle non contiguous array like 0,0,2,0,0,2.

[@sheetalshireen]

+Sheetal according to your code, its giving area = 0...please correct if something is missing

[@sheetalshireen]

lets take example of 1,0,1,0.. and when we run following line after reaching last 0 (i==3) else { area = arr[top] * i; }...it will give 1*3 = 3 (where arr[top] =1 & i =3)

[@justanaverageguy4739]

great sir great thank you

[@saumya1857]

Thankyou .you made DP so easy .

[@tatinenimaheshbabu7344]

Thanks for such a good video..

[@p111calcutta1]

good explanation, thanks !!

[@HadisKianpour-iw2ni]

why 8? i cant undrestand:(

[@GinoMtzRamos]

tushar, you are my hero

[@Hystrix008]

Nice explanation, thank you : )

[@nuamaaniqbal6373]

Thanks man!

[@hobokenbloomfiled8356]

Another way to find max area would be area = max ((min * length of longest consecutive array), (highestValue in the array))

[@hobokenbloomfiled8356]

***** so in your video the last histogram values are 0 0 3 4 2 4 According to my suggestion length of longest consecutive array is 4 min value in the consecutive array is 2 highest value is 4 area = max ((min * length of longest consecutive array), (highestValue in the array)) area = max((2*4),4) area = max(8,4) area = 8 Time complexity O(length of the histogram array) Another example histogram array values 0 6 0 2 1 0 length of longest consecutive array is 2 min value in the consecutive array is 1 highest value is 6 area = max ((min * length of longest consecutive array), (highestValue in the array)) area = max((1*2),6) area = max(2,6) area = 6 Correct me if my solution seems wrong.

[@hobokenbloomfiled8356]

***** Makes sense I did realize that once I posted the comment. Although we could still use the formula for each consecutive array and compare the current max to the previous max .. and at the end of the array we can get the max of the entire array. 9,0,3,3,3,3,,0,1,1,1,1,1,1,1,1 Set arrayMax = 0 First Check max(9,0) arrayMax = 9; Second Check max(9,12) arrayMax=12; Third Check max(12,8) arrayMax =12 end of the array return arrayMax; So my formula would change to arrayMax = max ((min value in consecutive array * length of consecutive array), arrayMax);

[@hobokenbloomfiled8356]

***** Agreed did not consider this use case. Yeah my solution would return 5 in this case . But the max area should be 6. Is that correct? I just went down the rabbit hole trying to come up with a solution to it. Thanks for all the use cases.

[@SanjayKumar-jz3gf]

Is there a way to find indexes of largest rectangle?

[@lakshaykapoor6559]

Just store the row no. when u update the max_area first time and last time. For column no. get the indexes of the array when u calculate its area in histogram.

[@andriibogachenko2537]

what if rows could be changing the places ? hm....

[@pavithras7936]

Max sum😍😍😍😍😍

[@surekhagaikwad2801]

how we can do it for parallelogram?

[@aatifnazar1766]

how do you represent parallelogram in a data structure?

[@pranjalabhishek7566]

In your videos there is one issue, You should first explain the approach on the basis of test cases and slowly move towards building the algorithm. I meant to say that how we can approach a new problem that should be discussed .The solutions to problem can be found anywhere but only to understand the journey which lead to that solution we watch the videos. Thanks

[@saikarthikcheedella4301]

thats really cool .....nice explination.

[@Ilsk8q]

You made it really easy to understand, thank you

[@glacieredge6311]

Nice video. And recthaangle. Haha 😀

[@karangautam8832]

anyone can tell me how to find starting index of rectangle in this question

[@ShinAkuma]

A noob programmer like me would take these few variable. startI , startJ and run a loop from startI=0 till less than maxArea startJ=0 till less than maxArea Search if all values in this range are 1's. If you find a 0. Just shift this whole Window accordingly till you find the rectangle. Though this probably isnt the best way to do it, but I'm a noob and that's how I did it.

[@rajeshpany7017]

It not working for all case

[@tapanjeetroy8266]

Thank you sir

[@1Kapachow1]

First of all, thanks for your videos, you've created a very wide collection :) Either you are missing a step or I'm missing something. Here's an example: I isolated the problem to a very simple test case. Imagine that your matrix is a very simple one 10 01 your first histogram will be: 10 max area is 1 using your accumulation method, the second histogram will become 11 the max area is 2 which brings us to final answer of 2, which is obviously not a valid answer. Am I missing something here ? Any feedback is welcome :)

[@1Kapachow1]

+Tushar Roy Thanks, now it makes sense :)

[@HarishAmarnath]

This is wrong ! If we swap index 2,4 to 1,4 we ll still get same answer , but the matrix is not all made of 1's ..check at 5:53

[@himeshk187]

Awesome !

[@aatifnazar1766]

mind = blown!

[@bryanbocao4906]

Maybe a 3D histogram?

[@diegocondori5673]

thanks :)

[@LearnAI-andML]

just Awsome

[@Simoni1203]

Better to explain the logics first before throwing in the solution.

[@ateamcoolboy5815]

Lmao love your videos and your hair

[@shivendrakadam7596]

I think time complexity is O(RC^2)

[@aquibansari3941]

Ye sahi banda h! Like comment if your think the same!

[@kalytheo]

Thank you for everything! You are amazing! However, I believe this theory does not work for the following example (the number of lines is n=5 and the number of columns is m=5): 5 5 0 1 0 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 1 1

[@TheBD0000]

it will work.. answer will be 10

[@vinayak186f3]

Thanks

[@vinayak186f3]

Keep visiting again n again you fool 😠

[@arka.outside]

You are GOD !

[@namangrover1989]

Time Complexity should be O( rows * cols^2)

[@gautamrchavan]

@2:44, the value should be 1

[@gautamrchavan]

***** sorry my bad. I didn't listen to it clearly. Btw, great set of videos. Keep up the good work.

[@suniljaiswal2471]

check the code here also if you want cpincpp.blogspot.com/2020/09/maximal-rectangle-in-given-matrix-with.html

[@amankumar-set]

But how to calculate max histogram area.😂

[@helloeveryone2749]

suppose my row value were 3 3 4 2 then max area acc to you would have been 8 but 9 is the max value.

[@AmitDhiman000]

+The rock first check the histogram area calculation algorithm video, then you will come to know every thing is proper.

[@lifecodesher5818]

are you a robot