Maximal Rectangle | Problems

Given a rows x cols binary matrix filled with '0's and '1's, find the largest rectangle containing only '1's and return its area. This extends the largest rectangle in histogram problem to 2D by treating each row as a histogram base.

Example:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6

Sample Input

—

Sample Output

—

Constraints

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

Test Cases

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

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.