codeloopback
Guide contents

Lesson 154 of 164

Maximal Square

Given a matrix of 0s and 1s, find the largest square that contains only 1s and return its area.

LeetCode: 221. Maximal Square

Example

Text
1 1 1 1 0
1 1 1 1 1         Output: 9   (a 3 × 3 square, for example the top-left one)
1 1 1 1 1
0 1 0 0 0

Brute force: grow a square from every cell

Use every 1 as the top-left corner of a square, and grow the square one row and column at a time while the new row and column are all 1s.

Java
public class Main {
    // true if the new bottom row and right column for a square of side size + 1 are all 1s
    static boolean canGrow(int[][] m, int r, int c, int size) {
        for (int k = 0; k <= size; k++) {
            if (m[r + size][c + k] != 1 || m[r + k][c + size] != 1) return false;
        }
        return true;
    }

    static int maximalSquare(int[][] m) {
        int rows = m.length, cols = m[0].length;
        int best = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                int size = 0;
                while (r + size < rows && c + size < cols && canGrow(m, r, c, size)) {
                    size++;
                }
                best = Math.max(best, size);
            }
        }
        return best * best;
    }

    public static void main(String[] args) {
        int[][] m = {{1, 1, 1, 1, 0}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {0, 1, 0, 0, 0}};
        System.out.println(maximalSquare(m));
    }
}
Output
9

Time: O(r · c · s²) for a largest square of side s. Space: O(1).

Optimal: grow squares from their neighbours

Let side[i][j] be the side of the largest all-1 square whose bottom-right corner is (i, j). If the cell is 1, that square is limited by the squares ending at its top, left, and top-left neighbours:

Text
side[i][j] = 1 + min(side[i-1][j], side[i][j-1], side[i-1][j-1])    if m[i][j] == 1
side[i][j] = 0                                                      otherwise

If all three neighbours end squares of side at least k, together they cover a (k + 1) × (k + 1) square ending at (i, j). If any of them is smaller, it has a 0 that also blocks the larger square.

Java
public class Main {
    static int maximalSquare(int[][] m) {
        int cols = m[0].length;
        int[] prev = new int[cols + 1]; // side[i - 1][..], shifted by one column
        int best = 0;
        for (int[] row : m) {
            int[] cur = new int[cols + 1];
            for (int j = 1; j <= cols; j++) {
                if (row[j - 1] == 1) {
                    cur[j] = 1 + Math.min(prev[j], Math.min(cur[j - 1], prev[j - 1]));
                    best = Math.max(best, cur[j]);
                }
            }
            prev = cur;
        }
        return best * best;
    }

    public static void main(String[] args) {
        int[][] m = {{1, 1, 1, 1, 0}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {0, 1, 0, 0, 0}};
        System.out.println(maximalSquare(m));
        int[][] m2 = {
            {0, 0, 0, 0, 1, 1},
            {0, 1, 1, 1, 1, 0},
            {0, 1, 1, 1, 1, 0},
            {0, 1, 1, 1, 1, 0},
            {1, 1, 1, 1, 1, 1},
            {1, 0, 0, 0, 0, 0},
        };
        System.out.println(maximalSquare(m2) + " " + maximalSquare(new int[][]{{0}}));
    }
}
Output
9
16 0

Time: O(r · c). Space: O(c): only the previous row is kept. An extra column of zeros on the left removes the special case for j = 0.

Edge cases