Geeks 面试题之Maximum size square sub-matrix with all 1s

Geeks 面试题之Maximum size square sub-matrix with all 1s2015-09-28

Maximum size square sub-matrix with all 1s

Given a binary matrix, find out the maximum size square sub-matrix with all 1s.

For example, consider the below binary matrix.

011011101001110 11110 11111 00000

The maximum square sub-matrix with all set bits is

111111111

Algorithm:
Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] where M[i][j] is the rightmost and bottommost entry in sub-matrix.

1） Construct a sum matrix S[R][C] for the given M[R][C]. a）Copy first row and first columns as it is from M[][] to S[][] b）For other entries, use following expressions to construct S[][] If M[i][j] is 1 thenS[i][j] = min（S[i][j-1], S[i-1][j], S[i-1][j-1]） + 1 Else /*If M[i][j] is 0*/S[i][j] = 02） Find the maximum entry in S[R][C]3） Using the value and coordinates of maximum entry in S[i], printsub-matrix of M[][]

For the given M[R][C] in above example, constructed S[R][C] would be:

 01101 11010 01110 11220 12231 00000

The value of maximum entry in above matrix is 3 and coordinates of the entry are （4, 3）. Using the maximum value and its coordinates, we can find out the required sub-matrix.

http://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/

本题和Leetcode上的找到最大面积不一样，这里是找最大的正方形。

不过比Leetcode上的那个题目要容易多了。

这里比原网站省内存，由O（m*n）降到O（n）.