Maximum size square sub-matrix with all 1s

Given a matrix of dimensions mxn having all entries as 1 or 0, find out the size of maximum size square sub-matrix with all 1s.

Algorithm:
1: Create an empty table of size mxn, defined as
table[i][j] = Size of maximum square sub matrix with all 1s with matrix[i][j] as bottom right element.
2: Set values in table based on the conditions
a: if i = 0 or j = 0, table[i][j] = matrix[i][j]
b: else if matrix[i][j] = 0 then table[i][j] = 0
c: else table[i][j] = min(table[i - 1][j - 1], table[i - 1][j], table[i][j - 1]) + 1;
During step 2, maintain largest element added in the table and finally return it.

Order of the Algorithm:
Time Complexity: O(mn)
Space Complexity: O(mn)

Code and Algorithm Visualization: http://www.ideserve.co.in/learn/maximum-size-square-sub-matrix-with-all-1s

Website: http://www.ideserve.co.in

Facebook: https://www.facebook.com/IDeserve.co.in

Видео Maximum size square sub-matrix with all 1s канала IDeserve