Example: Maximum sub‐square matrix

You are given a nxm 0/1 matrix and are tasking of finding the bigger nxn square matrix.

Let

• A(i,j) be the original matrix
• D(i,j) a matrix where D(i,j) represents the size of the largest sub-square matrix ending at cell (i,j)

Recursion relation:

• If A(i,j) == 0 => D(i,j) = 0
• If A(i,j) == 1 => D(i,j) = 1 + min(D(i-1,j), D(i-1,j-1), D(i,j-1))

Proof:

• If a square of size k ends at (i,j), then the top, left, and top-left sub-squares must at least be of size k-1.
• Conversely, if the minimum of top, left, top-left values is k-1 or larger, then a square of size k or larger can be formed at (i,j)

X:

0	0	1	1	1
1	0	1	1	1
0	1	1	1	1
1	0	1	1	1

D(i,j):

0	0	0	0	0	0
0	0	0	1	1	1
0	1	0	1	2	2
0	0	1	1	2	3
0	1	0	1	2	3

// x[0..n-1, 0..m-1]
minSubSquareMatrix(x)
    let d[0..x.len, 0..x[0].len]
    // initialize d to all 0
    int maxI = 0
    int maxJ = 0
    for i = 1 to x.len
        for j = 1 to x[0].len
            if (x[i-1,j-1] == 0)
                d[i,j] = 0
            else 
                d[i,j] = 1 + min(d[i, j-1], d[i-1, j-1], d[i-1, j])
                if(d[i,j] > d[maxI, maxJ])
                    maxI = i
                    maxJ = j
    print("MaxSize is: " + d[maxI, maxJ])