C# Solution for Maximal Rectangle Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition behind the C# solution is still to treat each row of the matrix as the ba
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition behind the C# solution is still to treat each row of the matrix as the base of a histogram and then apply the largest rectangle in histogram algorithm to find the maximum area rectangle that can be formed using that row as the base. However, instead of using nested loops, it uses a single loop for iterating through the matrix and updating the heights array.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tIterate through each row of the matrix.\n2.\tUpdate the heights array by incrementing the height if the corresponding matrix element is \u20181\u2019, or resetting it to 0 if it\u2019s \u20180\u2019.\n3.\tCalculate the maximum area using the largest rectangle in histogram algorithm for each updated heights array.\n4.\tUpdate and return the maximum area found.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\u2022\tLet n be the number of rows and m be the number of columns in the matrix.\n\u2022\tUpdating the heights array for each row takes O(m) time.\n\u2022\tCalculating the maximum area for each row takes O(m) time using the largest rectangle in histogram algorithm.\n\u2022\tTherefore, the total time complexity is O(n*m).\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\u2022\tWe use an additional heights array of length m to store the heights of the histogram.\n\u2022\tTherefore, the space complexity is O(m) since we only need to store the heights array.\n\n# Code\n```\npublic class Solution {\n    public int MaximalRectangle(char[][] matrix) {\n        if (matrix == null || matrix.Length == 0 || matrix[0].Length == 0) {\n            return 0;\n        }\n        \n        int rows = matrix.Length;\n        int cols = matrix[0].Length;\n        int maxArea = 0;\n        int[] heights = new int[cols];\n        \n        for (int i = 0; i < rows; i++) {\n            for (int j = 0; j < cols; j++) {\n                heights[j] = matrix[i][j] == \'1\' ? heights[j] + 1 : 0;\n            }\n            maxArea = Math.Max(maxArea, LargestRectangleArea(heights));\n        }\n        \n        return maxArea;\n    }\n\n    private int LargestRectangleArea(int[] heights) {\n        Stack<int> stack = new Stack<int>();\n        int maxArea = 0;\n        int i = 0;\n        \n        while (i < heights.Length) {\n            if (stack.Count == 0 || heights[stack.Peek()] <= heights[i]) {\n                stack.Push(i++);\n            } else {\n                int top = stack.Pop();\n                int area = heights[top] * (stack.Count == 0 ? i : i - stack.Peek() - 1);\n                maxArea = Math.Max(maxArea, area);\n            }\n        }\n        \n        while (stack.Count > 0) {\n            int top = stack.Pop();\n            int area = heights[top] * (stack.Count == 0 ? i : i - stack.Peek() - 1);\n            maxArea = Math.Max(maxArea, area);\n        }\n        \n        return maxArea;\n    }\n}\n```
['C#']