Java Clean Solution || Multiple Approaches and Detail Explanation
Intuition And Approach\nIf you\'re a coding enthusiast or a budding programmer, you\'ve probably heard about the Maximal Rectangle Problem. This fascinating pro
# Intuition And Approach\nIf you\'re a coding enthusiast or a budding programmer, you\'ve probably heard about the Maximal Rectangle Problem. This fascinating problem is a classic in the world of computer science and is often used to demonstrate the power of dynamic programming and efficient algorithm design.\n\nIn this blog post, we\'ll dive deep into the problem and explore a solution using a clever algorithm. We\'ll provide code examples in multiple programming languages to ensure that you can follow along regardless of your coding preferences. So, whether you\'re a C++ aficionado, a Java enthusiast, a Python pro, or a JavaScript wizard, you\'re in the right place!\n\n# Understanding the Maximal Rectangle Problem\nThe Maximal Rectangle Problem can be defined as follows: Given a binary matrix, find the largest rectangle containing only ones and return its area. This might sound a bit complex at first, but with the right algorithm, it becomes a manageable challenge.\n\n# The Algorithm: Dynamic Programming to the Rescue\nThe key to solving the Maximal Rectangle Problem lies in dynamic programming. Dynamic programming is a powerful technique that involves breaking down a complex problem into smaller subproblems and reusing solutions to subproblems to avoid redundant computations.\n\n# Step 1: The `largestRectangleArea` Function\nFirst, let\'s take a look at the `largestRectangleArea` function. This function, written in C++, Java, Python, and JavaScript, calculates the largest rectangle area in a histogram. The idea is to use a stack to efficiently find the maximum area.\n\nHere\'s a simplified overview of the algorithm:\n\n1. Create an empty stack to store indices.\n1. Iterate through the histogram from left to right.\n1. While the stack is not empty and the current histogram value is less than the value at the index stored in the stack\'s top element, pop elements from the stack and calculate the maximum area for each popped element.\n1. Keep track of the maximum area as you iterate through the histogram.\n1. This algorithm efficiently finds the largest rectangle area in the histogram, which we\'ll use in the next step.\n\n# Step 2: The `maximalAreaOfSubMatrixOfAll1` Function\nIn this step, we adapt the `largestRectangleArea` function to solve the Maximal Rectangle Problem for a binary matrix. We create a vector to store the height of each column and use dynamic programming to find the maximum rectangle area for each row.\n\n# Step 3: Bringing It All Together\nIn the final step, we create the maximalRectangle function, which takes a binary matrix as input and returns the maximum rectangle area containing only ones.\n\n# Dry Run of **`maximalRectangle`** Function\nWe\'ll perform a dry run of the `maximalRectangle` function using the following matrix:\n\n```\nmatrix = [\n    [\'1\', \'0\', \'1\', \'0\', \'0\'],\n    [\'1\', \'0\', \'1\', \'1\', \'1\'],\n    [\'1\', \'1\', \'1\', \'1\', \'1\'],\n    [\'1\', \'0\', \'0\', \'1\', \'0\']\n]\n```\n**Step 1: Initializing Variables**\nWe start with the given matrix:\n\n```\n1 0 1 0 0\n1 0 1 1 1\n1 1 1 1 1\n1 0 0 1 0\n```\nWe have two helper functions, largestRectangleArea and maximalAreaOfSubMatrixOfAll1, which are used within the `maximalRectangle` function.\n\nStep 2: maximalAreaOfSubMatrixOfAll1\nWe enter the maximalAreaOfSubMatrixOfAll1 function, which computes the maximal area of submatrices containing only \'1\'s.\n\nMatrix and height after each row iteration:\n\n1. Process Row 1:\n\n    - Matrix:\n```\n    1 0 1 0 0\n```\n    - Height: `[1, 0, 1, 0, 0]`\n1. Process Row 2:\n\n    - Matrix:\n``````\n1 0 1 1 1\n``````\n    - Height: `[2, 0, 2, 1, 1]`\n1. Process Row 3:\n\n    - Matrix:\n```\n1 1 1 1 1\n```\n    - Height: `[3, 1, 3, 2, 2]`\n1. Process Row 4:\n\n    - Matrix:\n```\n1 0 0 1 0\n```\n    - Height: `[4, 1, 1, 3, 1]`\n# Maximal Area of Histogram `(largestRectangleArea)`:\n\nFor each height, we calculate the maximal area of the histogram using the `largestRectangleArea` function.\n\nFor the height `[1, 0, 1, 0, 0]`, the maximal area is `1`.\nFor the height `[2, 0, 2, 1, 1]`, the maximal area is `4`.\nFor the height `[3, 1, 3, 2, 2]`, the maximal area is `6`.\nFor the height `[4, 1, 1, 3, 1]`, the maximal area is `4`.\nThe maximal area of submatrices for each row is `[1, 4, 6, 4]`.\n\n# Step 3: `maximalRectangle`\nFinally, we return the maximum value from the array `[1, 4, 6, 4],` which is `6`.\n\nThe maximal area of a submatrix containing only \'1\'s in the given matrix is `6`.\n\nThis concludes the dry run of the `maximalRectangle` function with the provided matrix.\n\n# Complexity\n- Time complexity:$$O(n*m)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    private int getMaximumArea(int[] height) {\n        Stack<Integer> stck = new Stack<>();\n        int area = 0;\n        for (int i = 0; i <= height.length; i++) {\n            while (!stck.isEmpty() && (i == height.length || height[stck.peek()] >= height[i])) {\n                int newHeight = height[stck.pop()];\n                int width = stck.isEmpty() ? i : i - stck.peek() - 1;\n                area = Math.max(area, width * newHeight);\n            }\n            stck.push(i);\n        }\n        return area;\n    }\n\n    public int maximalRectangle(char[][] matrix) {\n        int area = 0;\n        int[] height = new int[matrix[0].length];\n        for (int i = 0; i < matrix.length; i++) {\n            for (int j = 0; j < matrix[0].length; j++) {\n                if (matrix[i][j] == \'0\') {\n                    height[j] = 0;\n                } else if (matrix[i][j] == \'1\') {\n                    height[j]++;\n                }\n            }\n\n            int currentMaximumArea = getMaximumArea(height);\n            area = Math.max(area, currentMaximumArea);\n        }\n        return area;\n    }\n}\n```\n\n---\n\n\n```\nclass Solution {\n    private void getLeftBound(char[] matrix, int[] leftBound, int[] height, int left) {\n        for (int i = 0; i < height.length; i++) {\n            if (matrix[i] == \'1\') {\n                height[i]++;\n                leftBound[i] = Math.max(leftBound[i], left);\n            } else {\n                height[i] = 0;\n                leftBound[i] = 0;\n                left = i + 1;\n            }\n        }\n    }\n\n    private void getRightBound(char[] matrix, int[] rightBound, int right) {\n        for (int i = rightBound.length - 1; i >= 0; i--) {\n            if (matrix[i] == \'1\') {\n                rightBound[i] = Math.min(rightBound[i], right);\n            } else {\n                rightBound[i] = right;\n                right = i;\n            }\n        }\n    }\n\n    private int getMaximumArea(int[] height, int[] leftBound, int[] rightBound, int area) {\n        for (int i = 0; i < height.length; i++) {\n            int width = rightBound[i] - leftBound[i];\n            area = Math.max(area, height[i] * width);\n        }\n        return area;\n    }\n\n    public int maximalRectangle(char[][] matrix) {\n        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {\n            return 0;\n        }\n\n\n        int[] leftBound = new int[matrix[0].length];\n        int[] rightBound = new int[matrix[0].length];\n        int[] height = new int[matrix[0].length];\n\n        Arrays.fill(rightBound, matrix[0].length);\n        int area = 0;\n        for (int i = 0; i < matrix.length; i++) {\n            int left = 0;\n            int right = matrix[0].length;\n\n            getLeftBound(matrix[i], leftBound, height, left);\n            getRightBound(matrix[i], rightBound, right);\n\n            area = getMaximumArea(height, leftBound, rightBound, area);\n        }\n        return area;\n    }\n}\n```
['Array', 'Dynamic Programming', 'Stack', 'Matrix', 'Monotonic Stack', 'Java']