🔍

Max rectangle | Maximal Rectangle | Maximum Size Rectangle in Binary Matrix | DSA-One Course #45 - YouTube

Channel: Anuj Bhaiya

[0]

Hey what's up guys Anuj here &

[1]

Welcome to DSA one course &

[2]

in today's video, we will solve a question on stack

[4]

Largest Area submatrix with all 1s

[8]

here you are given a matrix

[9]

and you have to find which is the submatrix

[11]

that has the largest area

[13]

and what is it's area

[15]

so here you can see it is a matrix with a lot of 0s & 1s

[18]

and the largest area in it,

[20]

the largest rectangle or submatrix is there

[22]

whose area is the largest with all 1s

[24]

that is this one, 3 by 5

[26]

so the answer is 15

[28]

we also have some multiple rectangles in it

[29]

that has all 1s

[31]

as you can see this is also a rectangle of 1s here

[33]

it is of 6 by 2

[34]

whose area is 12

[35]

one more rectangle we have in this, that is this one

[37]

can you see? it's a 4 by 3 rectangle

[39]

it's area is also 12

[40]

there are many rectangles in it

[41]

many are of 2 by 2, one is of 3 by 3

[44]

here also we have one of 3 by 3

[45]

but the largest one is this 3 by 5 which has an area of 15

[49]

so this is our question

[50]

in this, we have one more question

[52]

that is the largest area square submatrix

[56]

square submatrix or largest square matrix

[59]

with all 1s

[61]

that question is slightly different from this

[63]

you can solve that question using dp

[65]

but we are not using that today,

[67]

we have a different question here

[68]

our question is submatrix

[69]

means rectangle

[71]

we can have a rectangle in this

[72]

when it is square, then it is easy, we can use dp & solve it

[76]

the method is different here

[78]

here the question is slightly different

[80]

when it is a rectangle

[82]

so how can we do this?

[83]

let me give you a hint

[85]

if you need a hint

[86]

this question will be solved like the last question we solved

[89]

in our last video,

[90]

which was the largest area histogram

[92]

using the same we will solve this

[94]

think about it how will we do this?

[95]

if you figured it out then that's too good

[97]

if you didn't don't worry I will show you

[99]

the logic & the best way to solve this

[102]

so basically what you have to do is,

[103]

you have to do it the same way we did the largest area in histogram

[106]

but how?

[107]

we have to go row by row

[109]

first go through this row

[110]

in the row on the top

[112]

and check if in this row

[114]

this was the base, this line here

[116]

if this line is the base

[119]

if this was our base

[120]

then, how many buildings are being made &

[121]

and from that buildings, what can be the largest area

[124]

so here I will make an array

[126]

this is our array

[128]

that is considering only the row on the top

[130]

for this row, suppose I gave you this question

[132]

you are given this array ok?

[133]

and for this, I asked you to find the largest area of the histogram

[139]

how will you do it?

[139]

so this question is similar to the previous one

[141]

that you have several buildings

[144]

and you are asked to find out the largest area

[148]

so these all are height 1

[150]

and here is a building of 0 height

[151]

so what will we find here?

[153]

so we have two fo 1 by 1

[154]

so our answer is 2

[156]

choose any of this, the answer will be 2

[158]

so here the answer will be 2

[160]

so you can say that here the answer is 2

[161]

so now let's go further down

[163]

now let's assume this is the base

[165]

now assume this new line is our base

[168]

so if this is our base, then what is the height of the buildings?

[170]

here the height is 2

[171]

here also the height is 2 but here it is 1

[174]

because here we do not have anything on the top of this

[175]

that is why here the height will be 1

[177]

so let's upgrade the array

[179]

initially we had 1,1,0,1,1

[180]

now it will be 2, because there was 1 on top of it

[183]

here also it will be 2

[186]

here it was previously 0, so we have an increment here

[190]

so it will be 1, here also it will be 2,

[193]

here also it will be 2

[195]

so now this is our array

[198]

if we solve it the same way so

[200]

it will be 2,2,1,2,2

[202]

so what will we get?

[203]

so 2 by 2 will be 4

[204]

and with 1, it will be 1 by 5

[206]

so 5 will be the area

[208]

so here our answer will be 5

[209]

how did we get 5?

[211]

we have something like this right?

[212]

2,2,1,2,2

[214]

so here we have 1 by 5

[216]

while here we have two areas of 2 by 2

[218]

and here we got 5

[220]

so here we saw for this base

[222]

this way we will keep moving downwards

[224]

now think of this base, what will it be here?

[227]

so for this base, it will be

[229]

here can you see it is zero?

[230]

as soon as you get zero,

[231]

do not consider the building above it

[233]

because if it is zero, there can't be any building on top of it

[236]

so when we get zero, we will not consider the building on top of it

[239]

there the height will be zero

[242]

so whenever we get zero, we will put 0 there

[244]

otherwise, if it is 1 then

[245]

increase it by 1 with what was on top of it

[247]

so here it was 2 on top, so it will be 3

[251]

here we had 1 already on top so it will increase by 1

[253]

so it will be 2

[254]

here we got 1, plus 2 which was on top

[256]

so it will be increased to 3

[257]

again here it will be increased to 3

[259]

so now our height is 0,3,2,3,3

[262]

so here we will have 2 multiplied by 4 which will be 8

[266]

or 3 multiplied by 2 which is 6

[270]

so here our answer will be 8

[273]

which one is it?

[275]

for this base, this rectangle of 2 by 4 which is 8

[277]

now again let's consider this our base

[281]

so for here, it is 1 so there will be an increment

[283]

it will be 1 instead of 0

[285]

here we will consider only height 1 for the building

[288]

because the above height was nulled due to zero

[290]

so the height will be 1

[291]

here it will be 4

[295]

here again it will increase to 3

[299]

the rest will also increase to 4 from 3

[302]

so here what answer can we have?

[303]

so we can have 3 by 4 which is 12

[306]

or 4 by 2 which is 8

[309]

12 is the largest so the answer will be 12

[312]

so 12 will be the answer & how?

[313]

here can you see this? 4 by 3

[316]

so this was we will keep moving

[317]

& for the baseline at the bottom, the answer will be 15

[320]

so you must have understood the logic

[322]

ok?

[322]

let me code this logic

[324]

code will be very simple

[325]

while coding, the previous question that we solved

[328]

the one about largest Histogram

[329]

we will use the same funda

[331]

we will plug in the same function here

[333]

and we will get our answer

[335]

this is a very fascinating & interesting question

[337]

let me code it

[339]

so I coded the same logic here

[341]

let's see how this logic is working here

[342]

so first of all, I made a current row

[345]

your current row will start from here ok

[347]

initially the current row will be the one on top

[349]

it will be a[0]

[350]

this 'a' is our matrix

[351]

after that we had our maximum answer

[353]

I initialized my maximum answer

[355]

that I initialised with maximum histogram

[357]

i did not code for maximum histogram

[359]

if you want the code for this, check out the previous video

[361]

the code is the same

[362]

basically it was the question on maximum histogram

[364]

in that you basically pass an array

[367]

& it tells us that if this array was a histogram

[369]

then what would have been the maximum area

[371]

this is that same code

[374]

we are calling that same code here

[375]

so our current row is 0,1,1,1,1,0

[381]

so for this array we ran this code

[384]

so this will return us the answer

[387]

suppose this is our current row

[388]

this is the current row

[392]

so here we will get the return, 4

[393]

so here the maximum answer we will get is 4

[396]

so this will be 4

[399]

[400]

then we will start from the next row

[402]

we will start from the next row

[403]

& what we will do is, we will go to each element one after the other

[407]

and we will upgrade our current row

[409]

how are we updating our current row?

[411]

we will check that if

[412]

the element in this index

[414]

if that element is 1

[416]

then we will increase the current row

[419]

if it is zero, then don't do anything

[420]

so let's see how it will be

[422]

so because this is 1,

[424]

so we will add it to the previous element

[425]

so the first value was zero,

[427]

it will increase to 1

[429]

so this will be

[430]

when 'i' was zero, it was like this

[432]

& when the value of 'i' will be 1,

[434]

then our current will be,

[436]

so here the value will be 1,

[438]

here also it is 1, so it will increase to 2

[441]

here also it is 1, so it will increase to 2

[443]

here also it will increase to 2

[444]

here it is zero, so it will be 0

[446]

here also it is 1, so it will increase to 1

[450]

when it is zero

[452]

we have to do something for that condition also

[454]

if a[i] is 1, then it is ok

[456]

else, current row equals to zero

[462]

I did not write this code

[463]

so here I added this else condition

[465]

that if it is 1

[466]

if any index is 1

[467]

then we will increase it's value

[469]

if there is zero,

[470]

then it will become zero

[472]

as here it was zero,

[473]

here also I wrote zero

[474]

now this is your array

[475]

& you will call the same code for this

[478]

the 'current answer= maximum histogram' one

[480]

maximum histogram that we solved in the previous video

[482]

we will call it for this array, so what answer will we get?

[485]

so for 1, we can get 1 multiplied by 4 which is 4

[488]

for 2, it can be 2 multiplied by 3 which is 6

[490]

so here the answer will be 6

[493]

so this will give us 6

[494]

let's go with 'i' equals to 2

[497]

let's move to the next row

[498]

again we will have our current array

[501]

we will upgrade it. How?

[503]

as here it is 1, we will increase it by 1, so this will be 2

[507]

here also it is 1, so it will increase to 3

[510]

here also it is zero, so it will become 0

[512]

here also it is 1, so it will increase to 3

[514]

here also it is 1, so it will increase to 1 from 0

[518]

here also it is 1, so it will increase to 2

[520]

so basically this is your array

[522]

if this was your base line

[524]

so can you see, here your length is 2

[526]

here the length is 3

[527]

here the length is 0

[529]

here the length is 3

[530]

here it is 1 & here the length is 2

[532]

so here we will make a histogram

[534]

so here what answer will we get?

[536]

so for 2, it will be 4

[538]

and for 1, it will be 3

[540]

so here it will be 4, ok?

[545]

and the maximum answer is still 6

[548]

which is 6?

[549]

6 is basically this one

[553]

now let's go to the next row

[554]

for 'i' equals to 3

[556]

let's see what will be the current here

[558]

so again because this is 1, so we will update it

[561]

it will be 3 instead of 2

[562]

here it will be updated to 4 from 3

[564]

here it will be updated from 0 to 1

[565]

here it will be updated to 4 from 3

[569]

here it will be updated to 2

[571]

it is zero, so this will be updated to zero

[573]

now let's see what answer will we get here

[576]

for 3, it will be 3x2=6

[579]

so this makes a 6 here

[580]

for 4, it will remain 4

[583]

for 1, it will be 5

[587]

or else, for 2 it can be 4

[590]

either this can be the answer for 2, which is 4

[593]

or for 1, 5 can be the answer

[595]

so the maximum answer here can be 3x2=6

[598]

this area

[599]

so here the answer will be 6

[600]

so the over all answer here will be

[602]

six

[603]

so there is two submatrix, one is this one of 3 by 2

[606]

or this one which is also 3 by 2

[609]

that is why our answer is 6

[611]

hope you guys have understood this code

[612]

it was very simple

[613]

if you want to see maximum histogram

[615]

then you can check out the previous video

[617]

there I have explained how to solve maximum histogram

[620]

that is using stack so

[621]

we have it here

[622]

ok?

[623]

so this was a very interesting question

[625]

i hope you have understood it

[626]

in the upcoming videos we will talk about prefix, postfix, infix

[631]

it is also solved using stack

[633]

if you understood everything then, do like this video

[635]

see you in the next video

[637]

on that note, Bye Bye.

Most Recent Videos:

WE KILLED 6 HEROIC BOSSES! - YouTube

¿Quién inventó el dinero? - YouTube

Cuándo se inventó el dinero y cómo el dólar se convirtió en la principal moneda del mundo - YouTube

This Citizenship Program is Failing - YouTube

Candida Treatment Protocol w/ Dr. DiNezza - YouTube

$500M investor reacts to Real Estate Tik Toks 2 - YouTube

You can go back to the homepage right here: Homepage