1

This is an interview question: given a boolean matrix find the size of the largest contiguous square sub-matrix, which contains only "true" elements.

I found this question on SO but did not understand the answer. The proposed algorithm moves a diagonal line from the left top to the right bottom and keeps track of the rectangles of "true" elements as the line goes.

My questions:

  • How to keep track of the rectangles in the algorithm?
  • Why do we move the diagonal line? What if we move a vertical/horizontal line or both?
  • How to calculate the algorithm complexity?
Community
  • 1
  • 1
Michael
  • 41,026
  • 70
  • 193
  • 341
  • 1
    duplicate: http://stackoverflow.com/questions/3806520/finding-maximum-size-sub-matrix-of-all-1s-in-a-matrix-having-1s-and-0s – Klark Jul 29 '12 at 19:35
  • @SINTER Thanks. The most interesting part of the answer is not clear though. They say there is a DP solution of O(N*N) for _square_ sub-matrix but did not elaborate on that. I think that is exactly I am looking for. – Michael Jul 30 '12 at 06:14

1 Answers1

4

I can't understand the answer in the link you posted, and I don't think the complexity given there is optimal for your problem. (It claim that there is an O(N^(3/2)*logN) algorithm where N=n*n is the number of elements in the original matrix.)

For your largest square sub-matrix problem, there is a DP algorithm whose complexity is linear with the number of elements:

Let the original matrix is A[n][n], we are trying to find a matrix B[n][n], where B[i][j] indicates the size of largest square sub-matrix whose bottom-right element is A[i][j]. So

for (i = 0 ; i < n ; ++i)
  for (j = 0 ; j < n ; ++j) 
    if (A[i][j] == 0) B[i][j] = 0;
    else {
      if (B[i-1][j] != B[i][j-1]) {
        B[i][j] = min(B[i-1][j], B[i][j-1]) + 1
      } else {
        if (A[i-B[i-1][j]][j-B[i-1][j]] == 1)
          B[i][j] = B[i-1][j] + 1;
        else
          B[i][j] = B[i-1][j];
      }
    }

And the largest B[i][j] is the answer.

p.s. I didn't check the array range for simplification. You can just consider the out-of-range elements are zero.

Community
  • 1
  • 1
RoBa
  • 418
  • 3
  • 6