Maximal Rectangle Problem: 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.
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.
Table of Contents
Maximal Rectangle Problem Solution
Problem Solution In Python
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
def largestRectangleArea(heights):
if not heights:
return 0
stack = [heights[0]]
maxi = 0
for item in heights[1:]:
if item >= stack[-1]:
stack.append(item)
else:
for i in range(len(stack)-1, -1, -1):
if stack[i] < item:
break
if i == 0:
i = -1
for j in range(i+1, len(stack)):
cur = stack[j]*(len(stack)-j)
if cur > maxi:
maxi = cur
for j in range(i+1, len(stack)):
stack[j] = item
stack.append(item)
for i in range(0, len(stack)):
cur = stack[i]*(len(stack)-i)
if cur > maxi:
maxi = cur
return maxi
if not matrix:
return 0
maxi_matrix = 0
for i in range(0, len(matrix)):
heights = [0 for _ in range(0, len(matrix[0]))]
for j in range(0, len(matrix[0])):
for k in range(i, -1, -1):
if matrix[k][j] == '1':
heights[j] += 1
else:
break
maxi_line = largestRectangleArea(heights)
if maxi_line > maxi_matrix:
maxi_matrix = maxi_line
return maxi_matrix
Problem Solution In Java
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) return 0;
int[][] m = new int[matrix.length][matrix[0].length];
for (int i = 0; i < m.length; i++) {
for (int j = 0; j < m[0].length; j++) {
if (matrix[i][j] == '0') continue;
m[i][j] = i > 0 ? m[i - 1][j] + 1 : 1;
}
}
int maxArea = 0;
for (int i = 0; i < m.length; i++) {
Stack<Integer> s = new Stack<>();
for (int j = 0; j <= m[0].length; j++) {
int h = j == m[0].length ? 0 : m[i][j];
if (s.isEmpty() || h >= m[i][s.peek()]) {
s.push(j);
} else {
int tp = s.pop();
maxArea = Math.max(maxArea, m[i][tp] * (s.isEmpty() ? j : j - 1 - s.peek()));
j--;
}
}
}
return maxArea;
}
Problem Solution In C++
int maxhist(vector<int> a)
{
stack<int> s;
int n = a.size(),i=0,t,area,maxarea=0;
while(i<n)
{
if(s.empty()|| a[s.top()] <= a[i]) s.push(i++);
else
{
t = s.top(); s.pop();
area = a[t] * (s.empty() ? i : i-s.top()-1);
maxarea = max(maxarea, area);
}
}
while(!s.empty())
{
t = s.top(); s.pop();
area = a[t] * (s.empty() ? i : i-s.top()-1);
maxarea = max(maxarea, area);
}
return maxarea;
}
int maximalRectangle(vector<vector<char>>& matrix) {
if(matrix.empty()) return 0;
int n = matrix.size(), m = matrix[0].size(),i,j;
vector<vector<int>> a(n, vector<int> (m));
for(i=0;i<n;i++)
{
for(j=0;j<m;j++) a[i][j] = matrix[i][j]-'0';
}
int result = maxhist(a[0]);
for(i=01;i<n;i++)
{
for(j=0;j<m;j++)
a[i][j] = (a[i][j] ? a[i][j]+= a[i-1][j] : a[i][j]);
result = max(result,maxhist(a[i]));
}
return result;
}
Problem Solution In C
typedef struct stack{
int top;
int capacity;
int* array;
}stack;
bool is_full(stack *s){
return s->top==s->capacity-1;
}
bool is_empty(stack *s){
return s->top==-1;
}
stack* create_stack(int capacity){
stack* s=(stack*)(malloc(sizeof(stack)));
s->capacity=capacity;
s->top=-1;
s->array=(int*)(calloc(sizeof(int), capacity));
return s;
}
void push(stack *s, int index){
if(is_full(s))
return;
s->array[++(s->top)]=index;
}
int pop(stack *s){
if(is_empty(s))
return -1;
return s->array[(s->top)--];
}
int peek(stack *s){
if(is_empty(s))
return -1;
return s->array[s->top];
}
int largestRectangleArea(int* heights, int heightsSize){
if(heightsSize==0)
return 0;
stack *s=create_stack(heightsSize);
int max_area=0;
int area=0;
int i=0;
int top=0;
for(i=0;i<heightsSize;){
if(is_empty(s) || heights[peek(s)]<=heights[i])
push(s, i++);
else{
top=pop(s);
if(is_empty(s))
area=heights[top]*i;
else
area=heights[top]*(i-peek(s)-1);
if(area>max_area)
max_area=area;
}
}
while(!is_empty(s)){
top=pop(s);
if(is_empty(s))
area=heights[top]*i;
else
area=heights[top]*(i-peek(s)-1);
if(area>max_area)
max_area=area;
}
free(s);
return max_area;
}
int maximalRectangle(char** matrix, int matrixSize, int* matrixColSize){
if(matrixSize==0 )
return 0;
int i=0,j=0;
int r=matrixSize, c=*matrixColSize, area=0, max_area=0;
int* dp=(int*)(calloc(sizeof(int),c));
for(i=0;i<r;i++){
for(j=0;j<c;j++){
if(matrix[i][j]=='0')
dp[j]=0;
else
dp[j]+=matrix[i][j]-'0';
}
area=largestRectangleArea(dp, c);
if(area>max_area)
max_area=area;
}
free(dp);
return max_area;
}