Last updated on March 7th, 2025 at 08:21 pm
Here, we see a Maximal Rectangle LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Array, Dynamic Programming, Hash Table, Stack
Companies
Level of Question
Hard
Maximal Rectangle LeetCode Solution
Table of Contents
1. 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
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is “Histogram-based Dynamic Programming”. This pattern is commonly used to solve problems involving maximal rectangles or areas in a 2D grid. The problem is broken down into smaller subproblems by treating each row of the matrix as the base of a histogram and calculating the largest rectangle in the histogram for each row.
3. Code Implementation in Different Languages
3.1 Maximal Rectangle 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;
}
};
3.2 Maximal Rectangle 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;
}
}
3.3 Maximal Rectangle 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;
};
3.4 Maximal Rectangle 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
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(m * n) | O(n) |
| Java | O(m * n²) | O(n) |
| JavaScript | O(m * n²) | O(n) |
| Python | O(m * n) | O(n) |
- C++ and Python implementations are more efficient with O(m * n) time complexity due to the use of a monotonic stack for histogram processing.
- Java and JavaScript implementations are less efficient with O(m * n²) time complexity due to the brute-force approach for calculating the maximal rectangle in the histogram.
- All implementations have a space complexity of O(n).