# Python simple O(mn) solution with detail explanation

• ``````class Solution(object):
def maximalRectangle(self, matrix):
"""
convert the 2D matrix to one dimensional arr,
then compute the max rectangle we can get in the one dimensional arr
:type matrix: List[List[str]]
:rtype: int
"""
if not matrix:
return 0
m, n = len(matrix), len(matrix[0])
line = [int(c) for c in matrix[0]]
res = self.getMaxMaxtrix(line)
for i in xrange(1, m):
for j in xrange(n):
if matrix[i][j] == '0':
line[j] = 0
else:
line[j] += 1
res = max(res, self.getMaxMaxtrix(line))
return res

def getMaxMaxtrix(self, arr):
"""
compute the max rectangle area in the one dimensional arr
the basic idea is to check each arr[index], find its left boundary(first left ele which is lower than it)
find its right boundary,then the area which extend based on index i is:
area = arr[i]*(right boundary - left boundary -1)
this can be done in O(n) for each index, so brute force solution is O(n^2)

we can do it in O(n) by leveraging stack to find its boundary.
walk through the arr from left to right,
we store index in the stack, and keep the arr[index] with ascending order, therefore, for each element in stack,
the former ele in stack is its left boundary, when the arr[i] is smaller than arr[stack[-1]],
we will pop it and compute the maximum rectangle we can construct based on this ele.
its right boundary is i (because arr[i]<arr[stack[-1]]), left boundary is its former ele in stack.
so we can compute its area

:param list[int]: the height of the building
:return: max area
"""
stack = []
res = 0
for i, h in enumerate(arr):
if i == 0:
stack.append(i)
else:
if arr[stack[-1]] <= h:
stack.append(i)
else:
while len(stack) != 0 and arr[stack[-1]] > h:
cur_h = arr[stack.pop()]
res = max(cur_h * (i - (stack[-1] if len(stack) != 0 else -1) - 1), res)
stack.append(i)
while len(stack) != 0:
cur_h = arr[stack.pop()]
res = max(cur_h * (len(arr) - (stack[-1] if len(stack) != 0 else -1) - 1), res)
return res
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.