Maximum size square sub-matrix with all 1s

The problem, simply

You get a grid of 0s and 1s with m rows and n columns. Find the biggest square block that is made only of 1s. Give back its side length.

Some versions (LeetCode 221) ask for the area. That is the side times itself.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every cell as the top left corner, and grow the square one size at a time until it hits a 0 or the edge.

1. For each cell with a 1, try sizes 1, 2, 3, and so on.
2. For each size, check every cell inside the square.
3. Stop growing when a check fails. Keep the biggest size that passed.

class Solution {
    public int maxSquare(int[][] mat) {
        int m = mat.length, n = mat[0].length, best = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int size = 1; i + size <= m && j + size <= n; size++) {
                    if (!allOnes(mat, i, j, size)) break;   // a puddle inside, stop growing
                    best = Math.max(best, size);
                }
            }
        }
        return best;
    }

    private boolean allOnes(int[][] mat, int r, int c, int size) {
        for (int i = r; i < r + size; i++)
            for (int j = c; j < c + size; j++)
                if (mat[i][j] == 0) return false;
        return true;
    }
}

How long it takes: m * n corners, up to min(m, n) sizes each, and a check of up to size * size cells, so O(m * n * min(m,n)^3). Extra room: O(1).

Way 2: the clever way

Make a table dp of the same shape. dp[i][j] is the side of the biggest all 1s square whose bottom right corner is cell (i, j).

1. In the top row and left column, dp equals the grid value.
2. If the grid has 0 at (i, j), then dp[i][j] = 0.
3. Otherwise dp[i][j] = 1 + min(up, left, up-left).
4. The answer is the biggest number in the table.

In the animation, the left grid is the lawn with the square found so far, and the right grid is the table being filled, with arrows from the three cells each answer comes from.

class Solution {
    public int maxSquare(int[][] mat) {
        int m = mat.length, n = mat[0].length, best = 0;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    dp[i][j] = 0;                          // a puddle ends nothing
                } else if (i == 0 || j == 0) {
                    dp[i][j] = 1;                          // top row or left column
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j],
                                   Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
                }
                best = Math.max(best, dp[i][j]);
            }
        }
        return best;
    }
}

How long it takes: each cell once, with three looks, O(m * n). Extra room: the table, O(m * n). Each row only needs the row above, so one row of n numbers plus one saved up-left value is enough.

Watch out for

• Return the biggest value anywhere in the table, not the bottom right cell.
• The first row and column must be copied, not left at 0, or a lone 1 there is missed.
• Area versus side: read which one is asked. LeetCode wants side * side.
• Grids of characters ('0' and '1') need mat[i][j] == '1', not == 1.

What interviewers ask next

• Count all squares of 1s (LeetCode 1277). Add up every dp[i][j]: a cell with value 3 is the corner of one square of each size 1, 2 and 3.
• The biggest rectangle of 1s instead? Build bar heights row by row and use the largest rectangle in a histogram with a stack, O(m * n).
• Use O(n) memory. Keep one row and a variable for the old up-left value before you overwrite it.
• Return where the square is. Remember (i, j) when best improves. The square spans rows i - best + 1 to i and the same for columns.

Remember this

Grown-up words: the lawn is a binary matrix, the blanket is a square sub-matrix, "ending at me" is the DP state for the bottom right corner, and the three friends are the cells the recurrence depends on.