Find max subsquare whose border values are all 1

Problem

Imagine you have a square matrix, where each cell is filled with either black or white. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.

Solution

We are going to scan column by column, checking to see if this column can be the left-border of the desired subsquare. Along each column, we build “sliding windows”, from large size to small size. The size of the window is the size of the subsquare. The winodw starts at different row, moving from top to bottom. When the window is fixed in a position, we chan check if this subsquare is valid or not. If so, we update the max subsquare we have found then continue.
Example:
111
011
000

1. 1st column:
   1. 1st row: window size = 3: {{1,1,1,},{0,1,1},{0,0,0}} is not valid; window size = 2: {{1,1,},{0,1}} is not valid; window size = 1: {{1}} is valid, so update it.
   2. 2nd row: window size = 2: {{0,1},{0,0}} is not valid; window size = 1: no need to check. already have a current max subsquare with size 1.
2. 2nd column:
   1. 1st row: window size = 2: {{1,1},{1,1}} is valid, so update it; window size = 1: no need to check.
   2. 2nd row: no need to check. Max subsquare can be found is of size 2, but we already have a valid one with size 2.
3. 3rd column:No need to check.

Java code

public static int[][] findMaxSubsquare(int[][] square) {
    int[][] maxSubsquare = null;
    int maxSize = 0;
    for (int col = 0; square.length - col > maxSize; ++col) {
        for (int row = 0; square.length - row > maxSize; ++row) {
            for (int size = square.length - Math.max(row, col); 
                        size > maxSize; --size) {
                if (isValidSubsquare(square, row, col, size)) {
                    maxSize = size;
                    maxSubsquare = new int[size][size];
                    for (int i = row; i < size + row; ++i)
                        System.arraycopy(square[i], col, maxSubsquare[i
                                - row], 0, size);
                }
            }
        }
    }
    return maxSubsquare;
}
 
private static boolean isValidSubsquare(int[][] square, int row, int col,
        int size) {
    // up and bottom border
    for (int j = col; j < col + size; ++j) {
        if (square[row][j] == 0)
            return false;
        if (square[row + size - 1][j] == 0)
            return false;
    }
    // left and right border
    for (int i = row; i < row + size; ++i) {
        if (square[i][col] == 0)
            return false;
        if (square[i][col + size - 1] == 0)
            return false;
    }
    return true;
}

References

• http://tianrunhe.wordpress.com/2012/06/11/find-max-subsquare-whose-border-values-are-all-1/