Algorithm

Problem Name: 85. Maximal Rectangle

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.

Example 1:

```Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.
```

Example 2:

```Input: matrix = [["0"]]
Output: 0
```

Example 3:

```Input: matrix = [["1"]]
Output: 1
```

Constraints:

• `rows == matrix.length`
• `cols == matrix[i].length`
• `1 <= row, cols <= 200`
• `matrix[i][j]` is `'0'` or `'1'`

Code Examples

#1 Code Example with C Programming

```Code - C Programming```

``````
int _min(int a, int b) {
return a < b ? a : b;
}
int _max(int a, int b) {
return a > b ? a : b;
}
int maximalRectangle(char** matrix, int matrixRowSize, int matrixColSize) {
int *dp, *left, *right, *height;
int i, j, l, r, k, m;

dp = malloc(matrixColSize * 3 * sizeof(int));
//assert(dp);
left = &dp[0];
right = &dp[matrixColSize];
height = &dp[matrixColSize * 2];

for (i = 0; i  <  matrixColSize; i ++) {
left[i] = 0;
right[i] = matrixColSize;
height[i] = 0;
}

m = 0;
for (i = 0; i  <  matrixRowSize; i ++) {
l = 0;
r = matrixColSize;
for (j = matrixColSize - 1; j >= 0; j --) {
if (matrix[i][j] == '1') {
right[j] = _min(right[j], r);  // on this height, from right to left, min index of '1'
} else {
right[j] = matrixColSize;
r = j;  // current row, from right to left, last one which is '0'
}
}
for (j = 0; j  <  matrixColSize; j ++) {
if (matrix[i][j] == '1') {
height[j] ++;
left[j] = _max(left[j], l);  // on this height, from left to right, max index of '1'

k = (right[j] - left[j]) * height[j];
m = m > k ? m : k;
} else {
height[j] = left[j] = 0;
l = j + 1;  // current row, from left to right, first one which is '0'
}
}
/*
for (j = 0; j  <  matrixColSize; j ++) {
printf("%d, ", right[j]);
}
printf("\n");
for (j = 0; j  <  matrixColSize; j ++) {
printf("%d, ", left[j]);
}
printf("\n");
for (j = 0; j  <  matrixColSize; j ++) {
printf("%d, ", height[j]);
}
printf("\n\n");
*/
}

free(dp);

return m;
}
``````
Copy The Code &

Input

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

Output

cmd
6

#2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if(matrix.size() == 0) return 0;
int m = matrix.size(), n = matrix[0].size(), maxArea = 0;
for(int i = 0; i < m; i++)
for(int j = 0; j  <  n; j++)
if(matrix[i][j] == '1') maxArea = max(maxArea, BFS(matrix, i, j));
return maxArea;
}

int BFS(vector < vector<char>>& matrix, int r, int c>{
int row = r - 1, maxArea = 0;
while(row >= 0 && matrix[row][c] == '1') row--;
for(int i = c; i >= 0 && matrix[r][i] == '1'; i--){
for(int j = row + 1; j  < = r; j++)
if(matrix[j][i] == '0') row = max(row, j);
maxArea = max(maxArea, (r - row) * (c - i + 1));
}
return maxArea;
}
};
``````
Copy The Code &

Input

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

Output

cmd
6

#3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const maximalRectangle = function(matrix) {
const m = matrix.length, n = matrix[0].length
const left = Array(n).fill(0)
const right = Array(n).fill(n - 1)
const height = Array(n).fill(0)

let res = 0

for(let i = 0; i  <  m; i++) {
let l = 0, r = n - 1
for(let j = 0; j  <  n; j++) {
if(matrix[i][j] === '1') left[j] = Math.max(left[j], l)
else {
left[j] = 0
l = j + 1
}
}

for(let j = n - 1; j >= 0; j--) {
if(matrix[i][j] === '1') right[j] = Math.min(right[j], r)
else {
right[j] = n - 1
r = j - 1
}
}

for(let j = 0; j < n; j++) {
height[j] = matrix[i][j] === '1' ? height[j] + 1 : 0
res = Math.max(res, (right[j] - left[j] + 1) * height[j])
}

// console.log(left, right, height>
}

return res
};
``````
Copy The Code &

Input

cmd
matrix = [["0"]]

#4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def maximalRectangle(self, matrix):
res, m, n = 0, len(matrix), len(matrix and matrix[0])
for i in range(m):
for j in range(n):
if matrix[i][j] != "0":
if j > 0 and matrix[i][j - 1] != "0":
matrix[i][j] = matrix[i][j - 1] + 1
else:
matrix[i][j] = 1
mn, sm, k = matrix[i][j], 0, i + 1
while k > 0 and matrix[k - 1][j] != "0":
if matrix[k - 1][j] < mn:
sm, mn = (i - k + 2) * matrix[k - 1][j], matrix[k - 1][j]
else:
sm += mn
if sm > res:
res = sm
k -= 1
return res
``````
Copy The Code &

Input

cmd
matrix = [["0"]]

#5 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;

namespace LeetCode
{
public class _085_MaximalRectangle
{
public int MaximalRectangle(char[][] matrix)
{
if (matrix.Length == 0) return 0;

int N = matrix.Length;
int M = matrix[0].Length;

int[] heights = new int[M];
var maxArea = 0;

for (int i = 0; i  <  N; i++)
{
for (int j = 0; j  <  M; j++)
heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0;
maxArea = Math.Max(maxArea, ComputeLargestRectangle(heights));
}

return maxArea;
}

private int ComputeLargestRectangle(int[] heights)
{
var stack = new Stack < int>();
stack.Push(-1);
int maxArea = 0;
for (int i = 0; i  <  heights.Length; i++)
{
while (stack.Peek() != -1 && heights[stack.Peek()] >= heights[i])
maxArea = Math.Max(maxArea, heights[stack.Pop()] * (i - stack.Peek() - 1));
stack.Push(i);
}
while (stack.Peek() != -1)
maxArea = Math.Max(maxArea, heights[stack.Pop()] * (heights.Length - stack.Peek() - 1));
return maxArea;
}
}
}
``````
Copy The Code &

Input

cmd
matrix = [["1"]]

Output

cmd
1