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


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment