Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example:


Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
     def maximalRectangle(self, matrix):
         """
         :type matrix: List[List[str]]
         :rtype: int
         """
         if not matrix or not matrix[0]:
             return 0
         n = len(matrix[0])
         height = [0] * (n + 1)
         ans = 0
         for row in matrix:
             for i in range(n):
                 height[i] = height[i] + 1 if row[i] == '1' else 0
             stack = [-1]
             for i in range(n + 1):
                 while height[i] < height[stack[-1]]:
                     h = height[stack.pop()]
                     w = i - 1 - stack[-1]
                     ans = max(ans, h * w)
                 stack.append(i)
         return ans

class Solution:
     def maximalRectangle(self, matrix):
         """
         :type matrix: List[List[str]]
         :rtype: int
         """
         if not matrix:
             return 0
         m = len(matrix)
         n = len(matrix[0])
         ans = 0
         heights = [0]*(n+1)
 
         for i in range(m):
             for j in range(n):
                 heights[j] = heights[j] + 1 if matrix[i][j] == '1' else 0
             stack = [-1]
             for i in range(n + 1):
                 while heights[i] < heights[stack[-1]]:
                     h = heights[stack.pop()]
                     w = i - stack[-1] - 1
                     ans = max(ans, w*h)
                 stack.append(i)
         return ans
                 


class Solution:
     
     def __init__(self):
         self.maxarea = 0
         
     def maximalRectangle(self, matrix):
         """
         :type matrix: List[List[str]]
         :rtype: int
         """
          
         if len(matrix) == 0 or len(matrix[0]) == 0:
             return 0
         
         def maxrect(height):
             height.append(0)
             stack = [-1]
             ans = 0
             for i in range(len(height)):
                 while height[i] < height[stack[-1]]:
                     h = height[stack.pop()]
                     w = i - stack[-1] - 1
                     ans = max(ans, h * w)
                 stack.append(i)
             height.pop()
             return ans
 
 
             
         
         abs_max = 0
         height = [0]*len(matrix[0])
         for i in range(len(matrix)):
             for j in range(len(matrix[0])):
                 if matrix[i][j] == "0":
                     height[j] = 0
                 else:
                     height[j] += 1
             local_max = maxrect(height)
             if local_max > abs_max:
                 abs_max = local_max
         
         return abs_max