03. Maximal Rectangle in 2D Binary Matrix

Difficulty:HardPattern:2D Matrix to Histogram DPTime:O(m * n)Space:O(n)

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.

How It Works & Algorithmic Design

Solves using Dynamic Row Histogram Updating + Histogram Stack:

Histogram Array: Maintain dp array of size cols initialized to 0.
Row Traversal: Loop row by row:
- For each cell in row: if matrix[r][c] === '1', dp[c] += 1; else dp[c] = 0.
- Calculate maxArea = Math.max(maxArea, largestRectangleArea(dp)) using Histogram Monotonic Stack.
Return: Maximum overall area found.

Why This Approach Works Best

Transforms 2D matrix search into $M$ consecutive histogram sub-problems executing in optimal $O(M \times N)$ time and $O(N)$ space.

Example Walkthrough

Input Matrix: [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

Binary grid.

Max Area: 3x2 rectangle of 1s yields 6 area.

Max contiguous rectangle.

Output: 6

Max rectangular area.

Answer: Maximal Rectangle implementation

function maximalRectangle(matrix) {
  if (!matrix.length || !matrix[0].length) return 0;
  const cols = matrix[0].length;
  const dp = new Array(cols).fill(0);
  let maxArea = 0;
  for (let r = 0; r < matrix.length; r++) {
    for (let c = 0; c < cols; c++) {
      dp[c] = matrix[r][c] === '1' ? dp[c] + 1 : 0;
    }
    maxArea = Math.max(maxArea, largestRectangleArea(dp));
  }
  return maxArea;
}

function largestRectangleArea(heights) {
  const stack = [];
  let maxArea = 0;
  const H = [...heights, 0];
  for (let i = 0; i < H.length; i++) {
    while (stack.length && H[stack[stack.length - 1]] > H[i]) {
      const h = H[stack.pop()];
      const w = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      maxArea = Math.max(maxArea, h * w);
    }
    stack.push(i);
  }
  return maxArea;
}

💡 Build height array per matrix row and evaluate largest histogram rectangle.

Key Takeaways

Converts 2D matrix search into 1D dynamic histogram problems.
Resetting column height to 0 on matrix cell '0' enforces contiguous 1s.
Time complexity $O(M \times N)$.