@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 <[email protected] > 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
