<p>Given a <code>rows x cols</code>&nbsp;binary <code>matrix</code> filled with <code>0</code>&#39;s and <code>1</code>&#39;s, find the largest rectangle containing only <code>1</code>&#39;s and return <em>its area</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/14/maximal.jpg" style="width: 402px; height: 322px;" />
<pre>
<strong>Input:</strong> matrix = [[&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;],[&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;],[&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;],[&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;]]
<strong>Output:</strong> 6
<strong>Explanation:</strong> The maximal rectangle is shown in the above picture.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> matrix = [[&quot;0&quot;]]
<strong>Output:</strong> 0
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> matrix = [[&quot;1&quot;]]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>rows == matrix.length</code></li>
	<li><code>cols == matrix[i].length</code></li>
	<li><code>1 &lt;= row, cols &lt;= 200</code></li>
	<li><code>matrix[i][j]</code> is <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
</ul>

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        pass

















class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        max_y, max_x = 1, 1

        @lru_cache(None)
        def recursion(y, x):
            nonlocal max_y, max_x
            if y < 0 or x < 0:
                return 0, 0

            min_y1, min_x1 = recursion(y-1, x)
            min_y2, min_x2 = recursion(y-1, x-1)
            min_y3, min_x3 = recursion(y, x-1)
            min_x = min(min_x1, min_x2, min_x3)
            min_y = min(min_y1, min_y2, min_y3)

            if matrix[y][x] == '1':
                min_x += 1
                min_y += 1
                max_y = max(max_y, min_y)
                max_x = max(max_x, min_x)
            else:
                min_x = 0
                min_y = 0
            return min_y, min_x
        
        recursion(len(matrix)-1, len(matrix[0])-1)
        return max_y * max_x
















class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        max_area = 0
        dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == '0':
                    continue
                
                if j >= 1:
                    width = dp[i][j] = dp[i][j-1] + 1
                else:
                    width = dp[i][j] = 1

                for k in range(i, -1, -1):
                    width = min(width, dp[k][j])
                    max_area = max(max_area, width * (i-k+1))
        return max_area


class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        if not heights:
            return 0 

        heights = heights + [0]
        stack = [-1]
        max_vol = heights[0]
        for i, h in enumerate(heights):
            while stack and stack[-1] != -1 and heights[stack[-1]] >= h:
                idx_popped = stack.pop()
                
                vol = (i - stack[-1] - 1) * heights[idx_popped]
                max_vol = max(max_vol, vol)
            stack.append(i)
        return max_vol

    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0

        max_area = 0
        dp = [0] * len(matrix[0])
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == '1':
                    dp[j] = dp[j] + 1
                else:
                    dp[j] = 0
            max_area = max(max_area, self.largestRectangleArea(dp))
        return max_area
























class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * n for _ in range(m)]
        max_area = 0
        for y in range(m):
            for x in range(n):
                if matrix[y][x] == '0':
                    continue
                
                dp[y][x] = dp[y][x-1] + 1 if x > 0 else 1
            
                min_w = dp[y][x]
                for yy in range(y, -1, -1):
                    min_w = min(min_w, dp[yy][x])
                    area = (y - yy + 1) * min_w
                    max_area = max(max_area, area)
        return max_area



class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [0] * n
        max_area = 0
        for y in range(m):
            for x in range(n):
                if matrix[y][x] == '1':
                    dp[x] = dp[x] + 1
                else:
                    dp[x] = 0
            
            area = self.hist(dp)
            max_area = max(max_area, area)
        return max_area
    
    def hist(self, dp):
        dp.append(0)
        max_area = 0
        stack = [-1]
        for i, h in enumerate(dp):
            while stack[-1] != -1 and dp[stack[-1]] >= h:
                idx_popped = stack.pop()
                area = (i - stack[-1] - 1) * dp[idx_popped]
                max_area = max(max_area, area)
            stack.append(i)
        return max_area





























class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        max_area = 0
        m, n = len(matrix), len(matrix[0])

        '''
        dp[y][x] stores length of continuous 1s in yth row, ending at xth col. 
        Continuous 1s is counted only at yth row, from left to right, ending at xth col. 
        See the figure in editorial. 
        '''
        dp = [[0] * n for _ in range(m)]
        
        for y in range(m):
            for x in range(n):
                if matrix[y][x] == '0':
                    continue
                
                if x == 0:
                    dp[y][x] = 1
                else:
                    dp[y][x] = dp[y][x-1] + 1
                
                width = dp[y][x]
                for k in range(y, -1, -1):
                    width = min(width, dp[k][x])
                    max_area = max(max_area, width * (y - k + 1))
        return max_area


class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        max_area = 0
        m, n = len(matrix), len(matrix[0])
        
        '''
        dp[x] counts the number of continuous 1s from to to the current row. 
        If you think it as an histogram, it is a rotated version of the historgram from editorial approach 2. 
        '''
        dp = [0] * n

        for y in range(m):
            for x in range(n):
                if matrix[y][x] == '1':
                    dp[x] = dp[x] + 1
                else:
                    dp[x] = 0
                
            max_area = max(max_area, self.hist(dp))
        return max_area
    
    def hist(self, dp):
        dp += [0]
        stack = [-1]
        max_area = 0
        for i, h in enumerate(dp):
            while stack[-1] != -1 and dp[stack[-1]] >= h:
                popped_idx = stack.pop()
                height = dp[popped_idx]
                if not stack:
                    break
                area = height * (i - stack[-1] - 1)
                max_area = max(area, max_area)
            stack.append(i)
        return max_area
























class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [0] * n
        max_area = 0
        for y in range(m):
            for x in range(n):
                if matrix[y][x] == '1':
                    dp[x] = dp[x] + 1
                else:
                    dp[x] = 0
            area = self.hist(dp)
            max_area = max(max_area, area)
        return max_area
    
    def hist(self, arr):
        arr += [0]
        stack = [-1]
        max_area = 0
        for i in range(len(arr)):
            while stack[-1] != -1 and arr[stack[-1]] >= arr[i]:
                idx_popped = stack.pop()
                area = arr[idx_popped] * (i - stack[-1] - 1)
                max_area = max(max_area, area)
            stack.append(i)
        return max_area

























class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [0] * n
        max_area = 0
        for y in range(m):
            for x in range(n):
                if matrix[y][x] == '1':
                    dp[x] += 1
                else:
                    dp[x] = 0
            area = self.hist(dp)
            max_area = max(max_area, area)
        return max_area
    
    def hist(self, arr):
        arr += [0]
        stack = [-1]
        max_area = 0
        for i in range(len(arr)):
            while stack[-1] != -1 and arr[stack[-1]] >= arr[i]:
                idx_popped = stack.pop()
                height = arr[idx_popped]
                area = height * (i - stack[-1] - 1)
                max_area = max(max_area, area)
            stack.append(i)
        return max_area


























class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [0] * n
        max_area = 0
        for y in range(m):
            for x in range(n):
                if matrix[y][x] == '1':
                    dp[x] += 1
                else:
                    dp[x] = 0
            area = self.hist(dp)
            max_area = max(max_area, area)
        return max_area

    def hist(self, arr):
        arr += [0]
        stack = [-1]
        max_area = 0
        for i, num in enumerate(arr):
            while stack[-1] != -1 and arr[stack[-1]] >= num:
                idx_popped = stack.pop()
                height = arr[idx_popped]
                area = height * (i - stack[-1] -1)
                max_area = max(max_area, area)
            stack.append(i)
        return max_area



class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        max_area = 0
        m, n = len(matrix), len(matrix[0])
        dp = [0] * n

        for y in range(m):
            for x in range(n):
                if matrix[y][x] == '1':
                    dp[x] += 1
                else:
                    dp[x] = 0
            area = self.hist(dp)
            max_area = max(max_area, area)
        return max_area
    
    def hist(self, arr):
        if not arr:
            return 0
        arr += [0]
        stack = [-1]
        max_area = 0
        for i in range(len(arr)):
            while stack[-1] != -1 and arr[stack[-1]] >= arr[i]:
                idx_popped = stack.pop()
                height = arr[idx_popped]
                area = height * (i - stack[-1] - 1)
                max_area = max(max_area, area)
            stack.append(i)
        return max_area






























class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [0] * n
        max_area = 0
        for y in range(m):
            for x in range(n):
                if matrix[y][x] == '1':
                    dp[x] += 1
                else:
                    dp[x] = 0
            area = self.hist(dp)
            max_area = max(max_area, area)
        return max_area

    def hist(self, arr):
        arr += [0]
        stack = [-1]
        max_area = 0
        for i in range(len(arr)):
            while stack[-1] != -1 and arr[stack[-1]] >= arr[i]:
                idx_popped = stack.pop()
                height = arr[idx_popped]
                area = height * (i - stack[-1] - 1)
                max_area = max(max_area, area)
            stack.append(i)
        return max_area

























class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [0] * n
        max_area = 0
        for y in range(m):
            for x in range(n):
                if matrix[y][x] == '1':
                    dp[x] += 1
                else:
                    dp[x] = 0
            max_area = max(max_area, self.hist(dp))
        return max_area
    
    def hist(self, arr):
        arr += [0]
        stack = [-1]
        max_area = 0
        for i, h in enumerate(arr):
            while stack[-1] != -1 and arr[stack[-1]] >= h:
                idx_popped = stack.pop()
                height = arr[idx_popped]
                area = height * (i - stack[-1] - 1)
                max_area = max(max_area, area)
            stack.append(i)
        return max_area



























class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [0] * n
        max_area = 0
        for y in range(m):
            for x in range(n):
                if matrix[y][x] == '1':
                    dp[x] += 1
                else:
                    dp[x] = 0
            max_area = max(max_area, self.hist(dp))
        return max_area

    def hist(self, arr):
        arr += [0]
        stack = [-1]
        max_area = 0
        for i, h in enumerate(arr):
            while stack[-1] != -1 and arr[stack[-1]] >= h:
                idx_popped = stack.pop()
                height = arr[idx_popped]
                area = height * (i - stack[-1] -1)
                max_area = max(max_area, area)
            stack.append(i)
        return max_area
    
18800