Algorithm
Problem Name: 85. Maximal Rectangle
problem Link: https://leetcode.com/problems/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.lengthcols == matrix[i].length1 <= row, cols <= 200matrix[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;
}
Input
matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output
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;
}
};
Input
matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output
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
};
Input
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
Input
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;
}
}
}
Input
matrix = [["1"]]
Output
1