# Leetcode Maximal Rectangle problem solution

Apr 25, 2023

In the Leetcode Maximal Rectangle problem solution 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’.

## Solution in C Programming

``````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;
}``````

## Solution in C++ Programming

``````class Solution {
int largestRectangleArea(vector<int>& heights) {
vector<int> st{-1};
int res = 0;

for (int i = 0; i < heights.size(); ++i) {
while (st.back() != -1 && heights[i] <= heights[st.back()]) {
int height = heights[st.back()];
st.pop_back();
int width = i - st.back() - 1;
res = max(res, height * width);
}
st.push_back(i);
}

while (st.back() != -1) {
int height = heights[st.back()];
st.pop_back();
int width = heights.size() - st.back() - 1;
res = max(res, height * width);
}

return res;
}

public:
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;

int m = matrix.size(), n = matrix[0].size();
vector<int> prevHeights(n, 0);
int res = 0;

for (int row = 0; row < m; ++row) {
vector<int> curHeights(n, 0);

// Update heights
for (int col = 0; col < n; ++col)
if (matrix[row][col] == '1')
curHeights[col] = prevHeights[col] + 1;

// Calculate current max rectangle
res = max(res, largestRectangleArea(curHeights));

// Set prevHeights
prevHeights = curHeights;
}

return res;
}
};``````

## Solution in Java Programming

``````class Solution {
public int largestRectangleArea(int[] heights) {
int n=heights.length;
int j=n-1;
int i=n-1;
Stack<Integer>s=new Stack<>();
s.push(i);
i--;
int nxtsr[]=new int [n];
nxtsr[j]=n;
j--;
while(i>=0){
if (s.size()==0){
nxtsr[j]=n;
s.push(i);
i--;
j--;
}
if (j<0)
break;
if (heights[i]>heights[s.peek()]){
nxtsr[j]=s.peek();
s.push(i);
j--;
i--;
}
else{
s.pop();
}
}
while (s.size()>0){
s.pop();
}
int nxtsl[]=new int [n];
i=0;
j=0;
nxtsl[0]=-1;
j++;
s.push(i);
i++;

while(i<n){
if (s.size()==0){
nxtsl[j]=-1;
s.push(i);
i++;
j++;
}
if (j==n)
break;
if (heights[i]>heights[s.peek()]){
nxtsl[j]=s.peek();
s.push(i);
j++;
i++;
}
else{
s.pop();
}
}
int maxarea=0;
for (int k=0;k<n;k++){
int width=nxtsr[k]-nxtsl[k]-1;
int area=width*heights[k];
if (area>maxarea)
maxarea=area;
}
return maxarea;
}
public int maximalRectangle(char[][] matrix) {
int []arr=new int[matrix[0].length];
int maxarea=Integer.MIN_VALUE;
for (int i=0;i<matrix.length;i++){
for (int j=0;j<matrix[0].length;j++){
if (matrix[i][j]=='0'){
arr[j]=0;
}
else {
arr[j]++;
}
}
int area=largestRectangleArea(arr);
if (area>maxarea)
maxarea=area;
}
return maxarea;
}
}``````

## Solution in Python Programming

``````# Monotonic Stack Solution!!!
class Solution(object):
def maximalRectangle(self, matrix):
if not matrix or not matrix[0]:
return 0
row,col = len(matrix),len(matrix[0])
res = float('-inf')
heights = [0 for _ in xrange(col)]  # initialize only one time !!!
for i in xrange(row):

for j in xrange(col):
heights[j] = heights[j] + 1 if matrix[i][j] == '1' else 0

heights.append(-1)

stack = []
for i,height in enumerate(heights):
while stack and height < stack[-1][0]:
r = i - 1
h = stack[-1][0]
l = 0
stack.pop()
if stack:
l = stack[-1][1] + 1
if res < (r - l + 1) * h:
res = (r - l + 1) * h
stack.append((height,i))
return res``````

## Solution in C# Programming

``````public class Solution  {
public int MaximalRectangle(char[][] matrix) {
if(matrix==null || matrix.Length==0)
return 0;
int max=0;
int[] heights=new int[matrix[0].Length];
for(int i=0;i<matrix.Length;i++)
{
for(int j=0;j<matrix[0].Length;j++)
{
heights[j] =matrix[i][j]=='0'?0:heights[j]+matrix[i][j]-'0';
//Console.WriteLine(heights[j]);
}

MAH obj=new MAH();

max=Math.Max(max,obj.LargestRectangleArea(heights));

}
return max;
}

public class  MAH{
public int LargestRectangleArea(int[] heights) {
if(heights==null || heights.Length==0)
return 0;
var nsl=NSL(heights);
var nsr=NSR(heights);

int max=0;
for(int i=0;i<heights.Length;i++)
{
max=Math.Max(max,(nsr[i]-nsl[i]-1)*heights[i]);
}
return max;
}
private int[] NSL(int[] arr)
{
Stack<Items> st=new Stack<Items>();
List<int> ls=new List<int>();

for(int i=0;i<arr.Length;i++)
{
if(st.Count==0)
{
}
else if(st.Count>0 && st.Peek().val<arr[i])
{
}
else if(st.Count>0 && st.Peek().val>=arr[i])
{
while(st.Count!=0 && st.Peek().val>=arr[i])
{
st.Pop();
}
if(st.Count==0)
{
}
else if(st.Peek().val<=arr[i])
{
}

}
Items newItem=new Items(){
val=arr[i],
index=i
};
st.Push(newItem);

}
return ls.ToArray();

}
private int[] NSR(int[] arr)
{
Stack<Items> st=new Stack<Items>();
List<int> ls=new List<int>();

for(int i=arr.Length-1;i>=0;i--)
{
if(st.Count==0)
{
}
else if(st.Count>0 && st.Peek().val<arr[i])
{
}
else if(st.Count>0 && st.Peek().val>=arr[i])
{
while(st.Count!=0 && st.Peek().val>=arr[i])
{
st.Pop();
}
if(st.Count==0)
{
}
else if(st.Peek().val<=arr[i])
{
}

}
Items newItem=new Items(){
val=arr[i],
index=i
};
st.Push(newItem);

}
ls.Reverse();
return ls.ToArray();
}

class Items
{
public int val;
public int index;
}

}
}``````

#### By Neha Singhal

Hi, my name is Neha singhal a software engineer and coder by profession. I like to solve coding problems that give me the power to write posts for this site.