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].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
