85. Maximal Rectangle

Solution 1: Brute-Force

# Convert to a "largest rectangle in histogram" problem

Time Complexity: O()
Space Complexity: O()

Solution 2: DP

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        lenRow = len(matrix)
        lenCol = len(matrix[0])
        hght = [0] * lenCol # record the current number of countinous '1' in column i;
        left = [0] * lenCol # record the left most index j which satisfies that for any index k from j to  i, height[k] >= height[i]
        rght = [lenCol - 1] * lenCol # record the right most index j which satifies that for any index k from i to  j, height[k] >= height[i]
        maxRectArea = 0 # we need to update maxArea with value (height[i] * (right[i] - left[i] + 1)) row by row
        
        for idxRow in range(lenRow):
            # 1. update height
            for idxCol in range(lenCol):
                if matrix[idxRow][idxCol] == '1':
                    hght[idxCol] += 1 # accumulate the height
                else:
                    hght[idxCol] = 0

            # 2. update left 
            currLftBound = 0
            for idxCol in range(lenCol):
                if matrix[idxRow][idxCol] == '1':
                    left[idxCol] = max(left[idxCol], currLftBound)
                else:
                    left[idxCol] = 0
                    currLftBound = idxCol + 1

            # 3. update right
            currRhtBound = lenCol - 1
            for idxCol in range(lenCol - 1, -1, -1):
                if matrix[idxRow][idxCol] == '1':
                    rght[idxCol] = min(rght[idxCol], currRhtBound)
                else:
                    rght[idxCol] = lenCol - 1
                    currRhtBound = idxCol - 1

            # 4. update max rectangle area
            for idxCol in range(lenCol):
                currRectArea = (rght[idxCol] - left[idxCol] + 1) * hght[idxCol]  
                maxRectArea = max(maxRectArea, currRectArea)

            # Debug Code
            # print("hght", hght)
            # print("left", left)
            # print("rght", rght)
            # print(maxRectArea)

        return maxRectArea

Time Complexity: O(M*N) // Iterate through M row * N col
Space Complexity: O(N) // Memo cumulate index of row[i], i from 0 to len(col size N)

Reference

https://medium.com/@ChYuan/leetcode-85-maximal-rectangle-%E5%BF%83%E5%BE%97-hard-73deebdc8752
https://leetcode.com/problems/maximal-rectangle/solutions/29054/share-my-dp-solution/

Follow-up 1: Maximal Square

Follow-up 2: Largest Rectangle in Histogram