# 85. Maximal Rectangle
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
Example:
Input:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Output: 6
# Solution
Approach 1: O(N^3)
: record the consecutive num of 1s for each row, and for each element go up to find the highest rectangle.
Approach 2: O(N^2)
: for each 1 in the matrix, record the max height above it (height of rectangle), and the left and right boundary where this max height extends to (width of rectangle).
Approach 3: O(N^2)
: Stack.
# Code (Python)
Approach 1:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if not matrix or not matrix[0]:
return 0
# O(N^3): record the consecutive num of 1s for each row, and for each element go up to find the highest rectangle
# S2 of https://leetcode.com/problems/maximal-rectangle/discuss/225690/Java-solution-with-explanations-in-Chinese
num_ones = [[0] * len(matrix[0]) for _ in range(len(matrix))]
max_area = 0
for r in range(len(matrix)):
for c in range(len(matrix[0])):
if c == 0:
num_ones[r][c] = 1 if matrix[r][c] == '1' else 0
else:
num_ones[r][c] = num_ones[r][c-1] + 1 if matrix[r][c] == '1' else 0
if num_ones[r][c] != 0:
width = num_ones[r][c]
for h in range(r, -1, -1): # need to account for every height above to avoid missing wide rectangles with high peaks
if num_ones[h][c] == 0:
break
width = min(width, num_ones[h][c])
max_area = max(max_area, width * (r - h + 1))
return max_area
Approach 2:
def maximalRectangle(self, matrix):
if not matrix or not matrix[0]:
return 0
# O(N^2): https://leetcode.com/problems/maximal-rectangle/discuss/29054/Share-my-DP-solution
# for each 1 in the matrix, record --
# the max height above it (height of rectangle), and
# the left and right boundary where this max height extends to (width of rectangle)
height, left, right = [0] * len(matrix[0]), [0] * len(matrix[0]), [len(matrix[0]) - 1] * len(matrix[0])
max_area = 0
for r in range(len(matrix)):
left_bound = 0
for c in range(len(matrix[0])):
if matrix[r][c] == '1':
height[c] = height[c] + 1
left[c] = max(left[c], left_bound)
else:
left_bound = c + 1
left[c] = 0
height[c] = 0
right_bound = len(matrix[0]) - 1
for c in range(len(matrix[0]) - 1, -1, -1):
if matrix[r][c] == '1':
right[c] = min(right[c], right_bound)
else:
right[c] = len(matrix[0])
right_bound = c - 1
max_area = max(max_area, (right[c] - left[c] + 1) * height[c])
return max_area
# Code (C++)
Approach 1:
Approach 2:
Approach 3:
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size();
if (m == 0) return 0;
int n = matrix[0].size();
if (n == 0) return 0;
int maxRect = 0;
vector<int> height(n, 0);
for (int i = 0; i < m; ++i)
{
stack<int> st;
for (int j = 0; j < n; ++j)
{
if (matrix[i][j] == '0')
height[j] = 0;
else
height[j]++;
}
for (int j = 0; j <= n; ++j)
{
while (!st.empty() && (j == n || height[st.top()] > height[j]))
{
int k = st.top();
st.pop();
int length = (!st.empty()) ? (j - st.top() - 1) : (j - 0);
maxRect = std::max(maxRect, length * height[k]);
}
st.push(j);
}
}
return maxRect;
}
};