Maximal Square

You are given an m × n grid matrix whose cells are the characters "0" and "1". Find the largest square (with sides parallel to the grid) that contains only "1" cells, and return its area, the number of cells it covers.

If the grid contains no "1" at all, return 0. Note that the cells are one-character strings, not numbers.

Example 1

Example 2

Example 3

Constraints

• 1 <= m, n <= 300
• matrix[i][j] is "0" or "1"

Pattern Path · Dynamic Programming · problem 156 of 169

Start simple

For every cell, try growing a square with that cell as its top-left corner and check each new row and column: O((mn)²) time in the worst case.

The key idea

Let side[i][j] be the side length of the largest all-ones square whose bottom-right corner is cell (i, j). For a "0" cell it is 0. For a "1" cell:

side[i][j] = 1 + min(side[i-1][j], side[i][j-1], side[i-1][j-1])

Why the minimum? A square of side s ending at (i, j) is made of the cell itself plus three overlapping squares of side s - 1 ending at the cell above, the cell to the left and the cell diagonally up-left. So s can be at most one more than each of those three values, and conversely, if all three neighbours support side s - 1, their squares together cover the whole s × s block. The weakest neighbour is the limit.

Filling the table row by row means the three neighbours are always ready. Padding the table with an extra zero row and column removes edge checks. The answer is the largest side seen, squared.

Complexity

• Time: O(m · n)
• Space: O(m · n) (O(n) with a single row)

Python

class Solution:
    def maximalSquare(self, matrix):
        rows, cols = len(matrix), len(matrix[0])
        # side[i][j]: largest square whose bottom-right corner is cell (i-1, j-1);
        # the extra zero row and column remove edge checks.
        side = [[0] * (cols + 1) for _ in range(rows + 1)]
        best = 0
        for i in range(1, rows + 1):
            for j in range(1, cols + 1):
                if matrix[i - 1][j - 1] == "1":
                    side[i][j] = 1 + min(side[i - 1][j], side[i][j - 1], side[i - 1][j - 1])
                    best = max(best, side[i][j])
        return best * best

JavaScript

var maximalSquare = function(matrix) {
  const rows = matrix.length, cols = matrix[0].length;
  // side[i][j]: largest square whose bottom-right corner is cell (i-1, j-1);
  // the extra zero row and column remove edge checks.
  const side = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));
  let best = 0;
  for (let i = 1; i <= rows; i++) {
    for (let j = 1; j <= cols; j++) {
      if (matrix[i - 1][j - 1] === "1") {
        side[i][j] = 1 + Math.min(side[i - 1][j], side[i][j - 1], side[i - 1][j - 1]);
        best = Math.max(best, side[i][j]);
      }
    }
  }
  return best * best;
};

What the interviewer is checking

This tests whether you can define a DP state that captures the right sub-structure (the square ending at a corner) and justify the min-of-three recurrence rather than just recite it.

Mistakes to avoid

• Returning the side length instead of the area.
• Comparing cells with the number 1 instead of the string "1".
• Using the max of the neighbours instead of the min.
• Index errors on the first row and column; a padded table avoids them.

Follow-ups to expect

• Reduce memory to one row. (Keep the old diagonal in a variable.)
• Find the largest all-ones rectangle. (Histogram + monotonic stack per row.)
• Count all all-ones squares. (Sum every side[i][j].)

In real software

Image processing and layout engines use this corner-based DP to find the largest uniform block, for example the biggest empty area on a map or a free region on a chip or warehouse floor plan.

Practice next