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 resSolution 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)
{
ls.Add(-1);
}
else if(st.Count>0 && st.Peek().val<arr[i])
{
ls.Add(st.Peek().index);
}
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)
{
ls.Add(-1);
}
else if(st.Peek().val<=arr[i])
{
ls.Add(st.Peek().index);
}
}
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)
{
ls.Add(arr.Length);
}
else if(st.Count>0 && st.Peek().val<arr[i])
{
ls.Add(st.Peek().index);
}
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)
{
ls.Add(arr.Length);
}
else if(st.Peek().val<=arr[i])
{
ls.Add(st.Peek().index);
}
}
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;
}
}
}Also read,