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

You're given a matrix of 0s and 1s. Find the biggest rectangular block made up entirely of 1s and return its area — essentially, locate the largest all-1s rectangle hiding anywhere in the 2D grid.

Input Format
Implement maximumSizeRectangleBinarySubMatrixWithAll1s(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 = [[0,1,1,0],[1,1,1,1],[1,1,1,1],[1,1,0,0]]
Output
8

Example 2

Input
matrix = [[0]]
Output
0
Constraints
  • 1 <= R, C <= 1000
  • matrix[i][j] is 0 or 1
Test Cases (2)
Case 1
Args: [[[0,1,1,0],[1,1,1,1],[1,1,1,1],[1,1,0,0]]] Expected: 8
Case 2
Args: [[[0]]] Expected: 0
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.

javascript
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