Maximal Square

The problem. Given an m × n binary matrix of "0"s and "1"s, find the largest square made only of 1s and return its area.

Example

matrix = [["1","0","1","0","0"],
          ["1","0","1","1","1"],
          ["1","1","1","1","1"],
          ["1","0","0","1","0"]]   ->  4
matrix = [["0","1"],["1","0"]]   ->  1
matrix = [["0"]]                 ->  0

The idea: the square ending at each cell

Let side[r][c] be the side of the largest all-ones square whose bottom-right corner is (r, c). If the cell is 0, it's 0. If it's 1, the square can grow only as far as its three neighbours allow — the squares ending to the left, above and above-left each limit it — so side[r][c] = 1 + min(left, above, above-left). The answer is the largest side anywhere, squared.

1. Grow a square from every corner

1function maximalSquare(matrix) {2  const m = matrix.length, n = matrix[0].length;3  let best = 0;4  for (let r = 0; r < m; r++) {5    for (let c = 0; c < n; c++) {6      let k = 0;                                   // try sides 1, 2, ... with top-left (r, c)7      grow: while (r + k < m && c + k < n) {8        for (let i = 0; i <= k; i++) {             // check the new bottom row and right column9          if (matrix[r + k][c + i] !== "1" || matrix[r + i][c + k] !== "1") break grow;10        }11        k++;12      }13      best = Math.max(best, k);14    }15  }16  return best * best;17}

Time O(m · n · min(m, n)²), space O(1). Each corner grows its square one ring at a time.

2. DP on the bottom-right corner

1function maximalSquare(matrix) {2  const m = matrix.length, n = matrix[0].length;3  const side = Array.from({ length: m }, () => new Array(n).fill(0));4  let best = 0;5  for (let r = 0; r < m; r++) {6    for (let c = 0; c < n; c++) {7      if (matrix[r][c] !== "1") continue;            // a 0 ends every square8      if (r === 0 || c === 0) side[r][c] = 1;        // on the edge: a 1x1 square at most9      else side[r][c] = 1 + Math.min(side[r - 1][c], side[r][c - 1], side[r - 1][c - 1]);10      best = Math.max(best, side[r][c]);11    }12  }13  return best * best;14}

Time O(m · n), space O(m · n) — or O(n) with one row plus a variable remembering the old above-left value. Why the minimum? A square of side s at (r, c) needs squares of side s − 1 ending at all three neighbours; the smallest neighbour is the limit.

Comparing the approaches

Edge cases to test

Variations