Find maximum submatrix containing like cells on the border

Question

The question is, given a matrix with all cells black or white, to find the maximum sized submatrix with all border cells black (the interior cells need not be black).

Currently I can at best think of an O(N^4) solution. For this, I make 2 auxiliary tables, one with count of consecutive black cells to the right in each row for each cell, and in the other, count of consecutive black cells in that column for each cell. Then I do it as follows:

for each row (i):
   for each cell (i,j):
     for each window (1..n-j):
       if auxrow[i,j+window]-auxrow[i,j] == window:   #so, all cells in this window is black
         colsleft = auxcol[i,j]
         colsright = auxcol[i,j+window]
         botttom_row = min(colsleft,colsright)
         for bot in (row..row+mincol):
            if auxrow[bot][j+window]-auxrow[bot][j] == window:
              maxlen = ... #do whatever to save this sub-matrix as answer

How to improve this solution? I saw some interesting discussion at Topcoder, particularly the answer by Rem (O(N^2*log N)), and the follow-up improvement suggested by Tomek, but I could understand neither solution! Can someone give a solution better than mine, or explain those algorithms?

Answer 1

O(N^3) is possible.

For each cell compute consecutive black cells to the top and right (can be done in O(N^2) time).

For each column (say column i) you get one array of n elements, which maintains the right information say R_i.

Now given the array R_i, we compute n other arrays (so Omega(N^3) space) as follows:

For each d such that 1 <= d <= n, you create a new array of n elements, D_id, which has a n+1 at element j if the corresponding value in R_i, ie R_i[j] < d. If R_i[j] >= d, then the corresponding entry in D_id will be equal to j.

Basically given a d and an i, using array D_id, we can tell what cell in the ith column can potentially be an endpoint of a rectangle of width d.

Now preprocess each D_id for range minimum queries: i.e given a range [u,v] we can find the minimum value in the sub-array D_id[u...v] in O(1) time.

Since you spend O(N^2) time for each column, this step is O(N^3) time.

Now to find a rectangle you consider each row and pick every pair of points which can for one edge of a rectangle. Consider these points to be the bottom left and bottom right end points of you rectangle.

Say the points in consider are on columns i and j and the width of the rectangle is d.

Now find the maximum possible height of the rectangle (using the top values we computed earlier). Say it was h.

Now if the row you are considering is r, you now run a range minimum query on D_id on the range (r, r-h]. If the minimum is <= n, then you have found a rectangle.

Since there are N^3 such possible pairs you will consider (N^2 points per row), the total running time is O(N^3).