## # 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:
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 = [ * len(matrix) for _ in range(len(matrix))]
max_area = 0
for r in range(len(matrix)):
for c in range(len(matrix)):
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:
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 =  * len(matrix),  * len(matrix), [len(matrix) - 1] * len(matrix)
max_area = 0
for r in range(len(matrix)):
left_bound = 0
for c in range(len(matrix)):
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) - 1
for c in range(len(matrix) - 1, -1, -1):
if matrix[r][c] == '1':
right[c] = min(right[c], right_bound)
else:
right[c] = len(matrix)
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.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;
}
};
``````