Maximal Rectangle with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nThis solution uses the concept of histogram to solve the problem. For eac
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nThis solution uses the concept of histogram to solve the problem. For each row, it converts the binary values into heights of the bars and then calculates the largest rectangle in the histogram using the stack data structure. The solution has a time complexity of O(n * m) and a space complexity of O(m).\n\n# Complexity\n- Time complexity:\n89.51%\n\n- Space complexity:\n85%\n\n# Code\n```\nclass Solution:\n    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n        if not matrix or not matrix[0]:\n            return 0\n        \n        n, m = len(matrix), len(matrix[0])\n        height = [0] * (m + 1)\n        ans = 0\n        \n        for row in matrix:\n            for i in range(m):\n                height[i] = height[i] + 1 if row[i] == \'1\' else 0\n            stack = [-1]\n            for i in range(m + 1):\n                while height[i] < height[stack[-1]]:\n                    h = height[stack.pop()]\n                    w = i - stack[-1] - 1\n                    ans = max(ans, h * w)\n                stack.append(i)\n        \n        return ans\n\n```
['Python', 'Python3']