Here, We see Maximal Rectangle LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
![Maximal Rectangle LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Maximal Rectangle LeetCode Solution
Table of Contents
Problem Statement
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
Maximal Rectangle Leetcode Solution C++
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int m = matrix.size(), n = matrix[0].size(), res = 0;
vector<int> heights(n, 0);
for (int i = 0; i < m; ++i) {
int ones = 0;
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == '0') heights[j] = 0;
else {
++ones;
++heights[j];
}
}
if (ones > 0) res = max(res, maxArea(heights)); // if all 0s in the row, no need to call the function
}
return res;
}
int maxArea(vector<int>& heights) { // copy paste from problem 84
int n = heights.size(), area = 0, h = 0, l = 0;
stack<int> stk;
for (int i = 0; i <= n; ++i) {
while(!stk.empty() && (i == n || heights[stk.top()] > heights[i])) {
h = heights[stk.top()]; stk.pop();
l = stk.empty() ? -1 : stk.top();
area = max(area, h * (i - 1 - l));
}
stk.push(i);
}
return area;
}
};
Code language: PHP (php)
Maximal Rectangle Leetcode Solution Java
class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0) return 0;
int ans = 0, m = matrix.length, n = matrix[0].length;
int[] height = new int[n]; // height
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '0') {
height[j] = 0;
continue;
}
height[j]++;
for (int cur = j - 1, pre = height[j]; cur >= 0; cur--) {
if (height[cur] == 0) break;
pre = Math.min(pre, height[cur]);
ans = Math.max(ans, (j - cur + 1) * pre);
}
ans = Math.max(ans, height[j]);
}
}
return ans;
}
}
Code language: JavaScript (javascript)
Maximal Rectangle Leetcode Solution JavaScript
var maximalRectangle = function(matrix) {
const n = matrix.length;
if (n === 0) return 0;
const m = matrix[0].length;
const h = new Array(n).fill(0);
let max = 0;
for (let j = 0; j < m; j++) {
for (let i = 0; i < n; i++) {
if (matrix[i][j] === '1') h[i]++;
else h[i] = 0;
}
for (let i = 0; i < n; i++) {
let k1 = i - 1;
while (k1 >= 0 && h[i] <= h[k1]) k1--;
let k2 = i + 1;
while (k2 < n && h[i] <= h[k2]) k2++;
max = Math.max(max, h[i] * (k2 - k1 - 1));
}
}
return max;
};
Code language: JavaScript (javascript)
Maximal Rectangle Leetcode Solution Python
class Solution(object):
def maximalRectangle(self, matrix):
maxVal = 0
out = 0
if matrix==[]:
return 0
minWidth = defaultdict(lambda: defaultdict(int))
for di in range(len(matrix)):
currW = len(matrix[0])
for dj in range(len(matrix[0])-1, -1, -1):
if matrix[di][dj] != "1":
minWidth[di][dj] = 0
else:
minWidth[di][dj] = 1
minWidth[di][dj] += minWidth[di][dj+1] if dj+1!=len(matrix[0]) else 0
maxArea = 0
for j in range(len(matrix[0])):
maxLeft = [-1]*len(matrix)
maxRight = [len(matrix)]*len(matrix)
stack = []
for i in range(len(matrix)):
while stack and minWidth[i][j] < minWidth[stack[-1]][j]:
maxRight[stack.pop()] = i
maxLeft[i] = stack[-1] if stack else -1
stack.append(i)
area = [(maxRight[i] - maxLeft[i] - 1)*minWidth[i][j] for i in range(len(matrix))]
maxArea = max(maxArea, max(area))
return maxArea
Code language: HTML, XML (xml)