Maximum Size Rectangle of All 1's Dynamic Programming

hello friends my name is Tushar and today I am going to discuss a question maximum size rectangle of all ones in a two dimensional matrix so you are given a two dimensional matrix matrix of zeros and ones and you have to find the maximum size rectangle of all ones in this matrix for example this is a rectangle of size 3 or this is a rectangle of size 6 so you have to find the rectangle which has the maximum size or of all ones in my another video I discussed how to find a maximum square of all one's in a two dimensional matrix but this question is different from that question so here we will use dynamic programming and maximum area rectangle in a histogram to solve this problem in another video I already discussed how to find a maximum area rectangle in a histogram but quickly let's quickly summarize it if you are given an array 3 2 3 2 this is the histogram you get when height is 3 and width is constant 1 the maximum area rectangle here will be of area 8 and this is that rectangle so we will use this algorithm and done in programming to solve this question this algorithm can this algorithm runs in O of n time so basically we can find the maximum area rectangle 0 of n time so let's solve this question here alright let's set another array of same size as a total number of columns in two-dimensional matrix so my array length is 6 going from 0 to 5 because I have 6 columns in my two-dimensional matrix first thing we do is we copy 0 through as it is there so this becomes 1 0 0 1 1 1 then I find a maximum area rectangle using this array so let's create a histogram for this so this becomes this looks something like 1 then 2 zeros then 1 1 1 so maximum here rectangle in this histogram is this and its area is 3 which is our max it is 0 so this is grid Axios maximum becomes three this can be found it off n time next let's bring Row 1 so if this value is 1 we go and add this value here so this becomes 2 if that's if this value is 0 so in the corresponding column here we make it 0 so this is already 0 if this is 1 we go to 2 and may add value here so this becomes 1 this is 1 so this becomes 2 this is 0 so this becomes 0 and this is 1 so this becomes 2 let's create another histogram based on this already 2 0 1 2 0 & 2 so the maximal area here we can get is off to either this one this one this one or this one and the max amount alone is 3 so will not change our max area let's bring row number 2 so if this value 0 let's make this Visio if this value is 1 we add it here so this becomes 1 if this value is 1 we added here so this becomes 2 if this value is 1 we added here so this becomes 3 if since this value is 1 we added here so this becomes 1 and this value is 1 so we added here so this becomes 3 let's create a histogram for this array so this is 0 then we have 1 then we have 2 then we have 3 then we have 1 and then we have 3 1 2 3 and 1 3 so the maximum area here is of area 5 and that is this area so since this is maximum axia five is greater than the max earphone too long so our max here becomes five all right let's bring the last row into that array so since this value is zero this becomes 0 this value is 0 so this becomes 0 this value is 1 so this becomes 3 this value is 1 so this becomes 4 this value is 1 so this becomes 2 and this value is 1 so this becomes 4 let's create a histogram based on this array the Instagram we look something like this 0 0 and then 3 and then 4 and then 2 and then for the maximum area here will be this one and this area will be 8 and that area is greater than the max later on till now so max your it becomes 8 so this is it the mass area rectangle max size rectangle in this two-dimensional matrix below be of size 8 and that rectangle is this one let's analyze the time and the space complexity the space complexity is pretty clear it's same as the total number of columns so our space complexity is off columns if the number of columns is way more than the number of rows then you can build you can sweep in this vertical fashion instead of sweeping in this horizontal fashion and in that case our space complexity we can become off rows the time complexity is for every row we are copying this information here so that XO of columns time and then we are finding a Mac cystogram so that also takes off columns time so our total time complexity is o of rows into columns the link to the code is in the description section of the video I would ask my viewers to like this video share it and subscribe to my youtube channel youtube.com user - Charlotte where if I transfer and will and visit my github link get up to our Commission peace interview wiki thanks for watching this video

Channel: Tushar Roy - Coding Made Simple

Views: 161,873

Rating: 4.9360728 out of 5

Keywords: maximum size rectangle of all 1s, largest rectangle of all 1s, largest rectangle in 2d matrix, dynamic programming

Id: g8bSdXCG-lA

Length: 6min 54sec (414 seconds)

Published: Thu May 14 2015