Problem statement

https://leetcode.com/problems/maximal-rectangle/

Solution

There is dp O(n^2m^2) solution. We can do better, with O(nm*min(m,n)) complexity, if we use dynamic programming and keep two tables: h[i][j] is the largest L, such that all elements in A[i:i+L-1][j] = 1, and similar w[i][j]. Then we go through our original table A and we can calculate for A[i][j] the largest subarray that has A[i][j] as its bottom-left corner, it can be done with O(n) iterations.

Finally, there is very smart way with complexity O(nm), using problem 0084. Indeed, for each row we can evaluate our skyline heights, given previous row in O(m) and do it n times. Additional complexity is O(m), because actually we need to keep only one row at at time.

Complexity

It is O(nm) for time and O(m) for space.

Code

class Solution:
    def maximalRectangle(self, matrix):
        def hist(heights):
            stack, ans = [], 0
            for i, h in enumerate(heights + [0]):
                while stack and heights[stack[-1]] >= h:
                    H = heights[stack.pop()]
                    W = i if not stack else i-stack[-1]-1
                    ans = max(ans, H*W)
                stack.append(i)
            return ans
        
        if not matrix or not matrix[0]: return 0
        m, n, ans = len(matrix[0]), len(matrix), 0
        row = [0]*m
        for i in range(n):
            for j in range(m):
                row[j] = 0 if matrix[i][j] == "0" else row[j] + 1
            ans = max(ans, hist(row))
            
        return ans