# Leetcode: Maximal Rectangle

Maximal Rectangle

Similar Problems:

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

For example, given the following matrix:

```1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
```

Return 6.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```## Blog link: https://code.dennyzhang.com/maximal-rectangle
## Basic Ideas: monotone stack
##       Based on another problem: https://code.dennyzhang.com/largest-rectangle-in-histogram
##
##       For each row, get the height
##       Find the max region of each row. Then get the global max
##
## Complexity: Time O(n*m), Space O(m)
class Solution(object):
def maximalRectangle(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
row_count = len(matrix)
if row_count == 0: return 0
col_count = len(matrix[0])
max_region = 0
for i in range(0, row_count):
for j in xrange(col_count):
matrix[i][j] = int(matrix[i][j])
# no need to add for first row
if i != 0:
if matrix[i][j] == 1:
matrix[i][j] += matrix[i-1][j]
max_region = max(max_region, self.largestRectangleArea(matrix[i]))
return max_region

def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
length = len(heights)
next_smallers = [-1] * length
stack = []
max_width = 0
# pad with fake items for the end
for i in xrange(length+1):
current = heights[i] if i != length else -1
# When heights[i] is not greater than the stack top, it's the target of stack top
while len(stack) != 0 and  current <= heights[stack[-1]]:
k = stack.pop()
h = heights[k]
left = -1 if len(stack) == 0 else stack[-1]
left = left + 1
right = i
max_width = max(max_width, h*(right-left))
stack.append(i)
return max_width
```

Share It, If You Like It.