Maximal Rectangle Problem Solution

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.

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