Maximal Rectangle | Problems

You're given a rows x cols matrix made up of the characters '0' and '1'. Find the biggest rectangular region made entirely of '1's and return its area. A useful way to think about this: each row can act as the base of a histogram built from consecutive 1s stacked above it, turning the problem into a 2D version of finding the largest rectangle in a histogram.

Input Format

Implement maximalRectangle(matrix). Inputs below show JavaScript function arguments; there is no stdin parsing.

Output Format

Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input

matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

Output

Example 2

Input

matrix = [["0"]]

Output

Constraints

1 <= rows, cols <= 200
matrix[i][j] is '0' or '1'

Test Cases (2)

Case 1

Args: [[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]] Expected: 6

Case 2

Args: [[["0"]]] Expected: 0

Topics

Dynamic Programming Memoization

Histogram per Row + Largest Rectangle in Histogram

javascript

function maximalRectangle(matrix) {
  if (!matrix.length) return 0;
  const n = matrix[0].length, heights = Array(n).fill(0);
  let max = 0;
  for (const row of matrix) {
    for (let j = 0; j < n; j++) heights[j] = row[j] === '1' ? heights[j] + 1 : 0;
    max = Math.max(max, largestRect(heights));
  }
  return max;
}
function largestRect(h) {
  const stack = [], n = h.length;
  let max = 0;
  for (let i = 0; i <= n; i++) {
    while (stack.length && (i === n || h[i] < h[stack[stack.length-1]])) {
      const height = h[stack.pop()];
      const width = stack.length ? i - stack[stack.length-1] - 1 : i;
      max = Math.max(max, height * width);
    }
    stack.push(i);
  }
  return max;
}

Time: O(mn) | Space: O(n)

Saved in this browser only. Private to you.