Leetcode Maximal Rectangle problem solution YASH PAL, 31 July 2024 In this Leetcode Maximal Rectangle problem solution we have 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. Topics we are covering Toggle Problem solution in Python.Problem solution in Java.Problem solution in C++.Problem solution in C. 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; } coding problems solutions