Determine the largest square of 1s in a binary matrix (a binary matrix only contains 0 and 1), return the length of the largest square.

Assumptions

• The given matrix is not null and guaranteed to be of size N * N, N > = 0

Examples

{ {0, 0, 0, 0},

{1,1, 1,1},

{0,1, 1,1},

{1, 0, 1, 1}}

the largest square of 1s has length of 2

Approach: DP. first line and first column, they are fixed. largest[0][n] = input[0][n] largest[n][0] = input[n][0]

largest[][] represents the largest square length at that position in input. consider the cordinates as the right bottom point of the square. length is determined by largest[i - 1][j], largest[i - 1][j - 1] and largest[i][j - 1]'s value

Deduction rule: largest[i][j] = min(largest[i - 1][j], largest[i - 1][j - 1] and largest[i][j - 1]) + 1 if input[i][j] is 1

                                                                                                                                                        otherwise = 0

public class Solution{
    public int largest(int[][] matrix) {
        int x = matrix.length;
        int[][] la = new int[x][x];
        int result = 0;

        for (int i = 0; i < x; i++) {
            for (int j = 0; j < x; j++) {
                if (i == 0) {
                    la[i][j] = matrix[0][j]
                }
                if (j == 0) {
                    la[i][j] = matrix[i][0];
                } else if (matrix[i][j] == 1) {
                    la[i][j] = Math.min(la[i - 1][j - 1] + 1, la[i][j - 1] + 1);
                    la[i][j] = Math.min(la[i][j], la[i - 1][j] + 1);
                    result = Math.max(result, la[i][j]);
                }
            }
        }
        return result;
    }
}

Time O(n^2)