Maximal Rectangle

Problem: Maximal Rectangle

First, we can consider maximal rectangle problem on a single row of a matrix first. When we deal with single row, we can simply expand a rectangle if we read consecutive one's and stop expanding when we met 0. We can keep modifying maximal rectangle when we walk through a row.

After we achieve maximal rectangle, it seems also simple to deal with the second row. Consider an example below:

0 1 1 0 1

0 0 1 1 0

For the first row, the maximal rectangle can be get from consecutive 2 ones. When we add the second row, we can see that for the 3rd element, we can see that we can get a rectangle of area two by adding the element above it. Thus, we can conclude that the area of maximal rectangle is decided by the ones on the same row and rows above it, which clearly can be solved by dynamic programming.

What we want to do is get width of a rectangle by going through a single row with consecutive positive numbers and get height of a rectangle by consecutive ones in a column.

Code in Python:

class Solution(object):
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        ans = 0
        if not matrix: return 0
        count = [0] * len(matrix[0]) + [-1]
        for row in matrix:
            for i in xrange(len(row)):
                count[i] += 1
                if row[i] == '0': count[i] = 0
            st = [(-1,-1)]
            for index, c in enumerate(count):
                while st[-1][1] > c:
                    ii, cc = st.pop()
                    ans = max(ans, cc*(index-st[-1][0]-1))
                st.append((index, c))
        return ans

For the example above, counts for row 0 are [0, 1, 1, 0, 1] and counts for row 1 are [0, 0, 2, 1, 0]. For the stack part, when we deal with row 0, we enter the while cause when we met the 3rd count as 0, and we get area of 2 at 2nd time entering the while cause, which means we first get 1 multiply 1, then 1 multiply 2. In this number, we actually store height of rectangle in counts. If the explanation is not clear enough, you can walk through it on your own.