Maximum size rectangle binary sub-matrix with all 1s Medium 0 attempts
GeeksforGeeks ↗

Maximum size rectangle binary sub-matrix with all 1s

Medium MatrixBFSDFS GeeksforGeeks

Given a binary matrix of 0s and 1s, find the maximum size rectangle containing all 1s and return its area. This is equivalent to finding the largest rectangle in a 2D binary matrix.

Example:

Input: matrix = [[0,1,1,0],[1,1,1,1],[1,1,1,1],[1,1,0,0]]
Output: 8
Sample Input
—
Sample Output
—
Constraints
  • 1 <= R, C <= 1000
  • matrix[i][j] is 0 or 1
Test Cases
Case 1
Args: [[[0,1,1,0],[1,1,1,1],[1,1,1,1],[1,1,0,0]]] Expected: 8
Topics
MatrixBFSDFS

Approach: Histogram per Row + Stack

Build a heights array where heights[j] is the number of consecutive 1s above (inclusive) for each row. Apply the largest-rectangle-in-histogram algorithm using a monotonic stack for each row.

function maximumSizeRectangleBinarySubMatrixWithAll1s(matrix) {
  if (!matrix.length) return 0;
  const n = matrix[0].length;
  const heights = new 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;
    const stack = [-1];
    for (let j = 0; j <= n; j++) {
      const h = j === n ? 0 : heights[j];
      while (stack.length > 1 && heights[stack[stack.length-1]] > h) {
        const height = heights[stack.pop()];
        const width = j - stack[stack.length-1] - 1;
        max = Math.max(max, height * width);
      }
      stack.push(j);
    }
  }
  return max;
}

Time Complexity: O(m × n)

Space Complexity: O(n)

Saved in this browser only. Private to you.

JavaScript