Maximal rectangle

Hard TimeO(n·m) SpaceO(m)

Given a grid matrix of 1s and 0s, return the area of the largest solid rectangle of 1s in it. The rectangle has to be solid — every cell inside it a 1 — its sides run along the rows and columns so it is never tilted, and its area is width times height counted in cells.

Examples

Example 1

Input
matrix = [[1, 0, 1, 0, 0], [1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0]]
Output
6
Rows 1 and 2, columns 2 to 4: 3 × 2 = 6 cells, every one of them a 1.

Example 2

Input
matrix = [[0, 0], [0, 0]]
Output
0
Not a single 1, so there is no rectangle and the area is 0.

The Code

function maximalRectangle(matrix) {
  if (matrix.length === 0) return 0;
  const width = matrix[0].length;
  const heights = new Array(width).fill(0);
  let best = 0;
  function largestInRow() {
    const stack = [];
    let area = 0;
    for (let i = 0; i <= width; i++) {
      const current = i === width ? 0 : heights[i];
      while (stack.length > 0 && heights[stack[stack.length - 1]] >= current) {
        const top = stack.pop();
        const left = stack.length === 0 ? -1 : stack[stack.length - 1];
        const candidate = heights[top] * (i - left - 1);
        if (candidate > area) area = candidate;
      }
      stack.push(i);
    }
    return area;
  }
  for (let r = 0; r < matrix.length; r++) {
    for (let c = 0; c < width; c++) {
      heights[c] = matrix[r][c] === 1 ? heights[c] + 1 : 0;
    }
    const area = largestInRow();
    if (area > best) best = area;
  }
  return best;
}
maximalRectangle([[1, 0, 1, 0, 0], [1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0]]);
Done

The first 30 calls, of 98. This one does not fit on a page.

Step through maximalRectangle([[1, 0, 1, 0, 0], [1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0]]) call by call

More like this

All matrices & grids examples (7) →