'''
keys: 
Solutions:
Similar:
T:
S:
'''
from typing import List


class Solution:
    # dp: maximum height at each point
    # T: O(NM); S: O(M) as the number of cols
    # https://leetcode.com/problems/maximal-rectangle/discuss/29054/Share-my-DP-solution
    def maximalRectangle2(self, matrix: List[List[str]]) -> int:
        if not matrix: return 0
        
        r = len(matrix); c = len(matrix[0])
        # leftmost and rightmost boundary
        left = [0] * c; right = [c] * c; height = [0] * c
        
        maxarea = 0
        for i in range(r): # top -> down loop
            cur_left, cur_right = 0, c
            # update the height
            for j in range(c):
                if matrix[i][j] == "1": 
                    height[j] += 1
                else: height[j]= 0
            # update left
            for j in range(c): # new_left = max(old_left, cur_left)
                if matrix[i][j] == "1": 
                    left[j] = max(left[j], cur_left)
                else: 
                    left[j] = 0 # making the possible left the leftmost
                    cur_left = j + 1
            # update right
            for j in range(c-1, -1, -1):
                if matrix[i][j] == "1": 
                    right[j] = min(right[j], cur_right)
                else:  
                    right[j] = c # making the possible right the rightmost
                    cur_right = j
            # update the area
            for j in range(c):
                maxarea = max(maxarea, height[j] * (right[j] - left[j]))
        return maxarea
    
    
    # using stack on histograms
    # T: O(N*M), run leetcode84 on each row takes M (length of row)
    # S: O(M), allocate an array the size of the the number of columns to store our widths at each row. 
    def maximalRectangle1(self, matrix: List[List[str]]) -> int:
        if not matrix: return 0
        maxarea = 0
        dp = [0] * len(matrix[0]) # a vector of total "cols" values
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                # update the state of this row's histogram using the last row's histogram
                # by keeping track of the number of consecutive ones
                dp[j] = dp[j] + 1 if matrix[i][j] == '1' else 0
                
            # update maxarea with the maximum area from this row's histogram
            maxarea = max(maxarea, self.leetcode84(dp))
        return maxarea
        
    def leetcode84(self, heights):
        heights.append(0)
        stack = [-1]
        maxArea = 0
        for i in range(len(heights)):
            while heights[i] < heights[stack[-1]]:
                h = heights[stack.pop()]
                w = i - stack[-1] - 1
                maxArea = max(maxArea, h * w)
            stack.append(i)
        heights.pop() # pop the 0 one added on the top, works even wo it
        return maxArea
        
    
    # 2D DP, quick slow...
    # keeping track of the number of consecutive ones each square in each row. 
    # O(n^2*m): 
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix: return 0
        maxarea = 0
        c = len(matrix[0]); r = len(matrix)
        dp = [[0] * c for _ in range(r)] # for store the maxwidth
        for i in range(r):
            for j in range(c):
                if matrix[i][j] == "0":
                    continue
                
                # compute the max width and update dp
                dp[i][j] = dp[i][j-1] + 1 if j else 1
                width = dp[i][j]
                
         # compute the max area rectangle with a lower right corner at [i, j]
                for row in range(i, -1, -1):
                    width = min(width, dp[row][j]) # find the width
                    maxarea = max(maxarea, width * (i-row+1))
        return maxarea
            
    
    # brutal force: N^3*M^3, N as num of rows and M as num of cols
    # all rectangles: O(N^2*M^2), iterating all these: O(M*N)