2 things 1. There was a small type in end where I said Time complexity :O ( 2 * m * n ) , actually its space complexity. Time complexity is O ( m * n^2 )
2. I got some requests to explain this with an example so I solved this for a matrix which is as following 0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 I have uploaded solution at http://groups.google.com/group/algogeeks/web/binaryMatrix_Rectangle.pdf plz review . -Manish On Nov 2, 9:02 am, Ankit Babbar <ankitbabba...@gmail.com> wrote: > @Modeling Expert: Can you please explain your algo with an example... > > especially calculating the area of rectangles using min depth and its > traversal through the matrix... > > On Tue, Oct 5, 2010 at 7:24 PM, Modeling Expert <cs.modelingexp...@gmail.com > > > > > wrote: > > For square matrix , link suggested by Amit would work. Finding a sub- > > rectangle is tougher. > > > I would go this way; First scan from bottom right till top left and > > for every Non-zero member in matrix create this pair ( width , > > depth ). > > > Width is how many continuous 1's ( including itself ) are there to > > its right, > > Depth is how many continuous 1's ( including itself ) are there down > > wards > > > now select a point P(i,j) , which has value Pair ( W , D ) it means > > W-1 columns to right and D-1 rows below are '1' , Note: it doesn't > > give any info about diagonal > > entries to P , and we will see , > > we actually don't need them. > > > Now think about all possible rectangles which could be made when P is > > left top corner > > so go columnwise from i to i + 1 , i +2 , i + (W-1) points ( call > > it P' point ) , at every step, see the minimum depth for all points > > between P and P' and keep calculating area by width X minDepth > > > e.g. P has width = 3, depth = 4 and co-ordinates (i,j ) then go like > > this > > Area for A[i,j] and P'[i, j+1 ] = 2 X MinDepth( P, P') //A1 > > Area for A[i,j] and P"[i, j+2 ] = 3 X MinDepth( P, P', P") //A2 : > > Note MinDepth is Minimum Depth of all three points so far > > Take Max of A1,A2 and you would have max rectangle which could be > > created by having P as top left corner. > > > Now , keep traveling P throughout this Matrix. > > > There are few optimisation. A point with width W and depth D can AT > > MAX has a rectangle with AREA MAX = W * D so next time consider points > > only whose W * D > Max Area calcuated so far.E.g if you have already > > got a point which has sub rectangle with area = 12 no need to look for > > points which has such (W,D) pairs = ( 2,3) , (4,2) , (3,3) etc . > > > Time complextiy : > > First time reverse traversal O(m * n ) /// m Rows , n Columns > > Second time , MAX AREA calculation for each points , worse case > > o(n) as we need to travel only column wise as explained above > > Above action to be done for m*n points so total O( mn * n ) = > > O(mn^2) > > > So total Time = O ( m * n^2 ) > > > Time complexity :O ( 2 * m * n ) as W and D pair for each entry has to > > be maintained > > > Suggestions, Clarifications, Modifications ? > > -Manish > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > Regards, > Ankit Babbar -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
