Maximal Rectangle

• Initialize maxArea to 0.
• If the matrix is empty, return 0.
• Get the number of rows and columns.
• Create a 2D integer array width of the same dimensions as the input matrix.
• Precompute the width array. For each row i, iterate from right to left (from j = cols - 1 to 0):
  • If matrix[i][j] is '1', set width[i][j] to 1 + width[i][j+1]. If j is the last column, it's just 1.
  • If matrix[i][j] is '0', set width[i][j] to 0.
• Iterate through each cell (i, j) of the matrix, considering it as a potential top-left corner of a rectangle.
• For each (i, j):
  • Initialize minWidth to a very large value.
  • Iterate downwards from the current row k = i to the last row.
    • Update minWidth to be the minimum of its current value and width[k][j]. This minWidth represents the width of the rectangle that spans from row i to k starting at column j.
    • If minWidth becomes 0, it means the rectangle is broken, so we can break the inner loop.
    • Calculate the height of the current rectangle as k - i + 1.
    • Calculate the area as minWidth * height.
    • Update maxArea with the maximum area found so far.
• Return maxArea.

A brute-force solution would be to check every possible rectangle, which is highly inefficient. We can improve this by fixing the top-left corner and the height of the rectangle and then finding the maximum possible width.

This approach pre-calculates, for each cell (i, j), the number of consecutive '1's to its right, including itself. Let's call this width[i][j]. This precomputation step takes O(rows * cols) time.

After precomputation, the main algorithm iterates through every cell (i, j) as a potential top-left corner. For each (i, j), it iterates downwards to every possible bottom row k. For a rectangle defined by top-left (i, j) and bottom row k, the height is k - i + 1. The width is limited by the narrowest stretch of '1's starting from column j in any row from i to k. This is equivalent to min(width[i][j], width[i+1][j], ..., width[k][j]). We calculate this area and update our global maximum.

1class Solution {2    public int maximalRectangle(char[][] matrix) {3        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {4            return 0;5        }6        int rows = matrix.length;7        int cols = matrix[0].length;8        int[][] width = new int[rows][cols];9 10        // Precompute width of consecutive '1's to the right11        for (int i = 0; i < rows; i++) {12            for (int j = cols - 1; j >= 0; j--) {13                if (matrix[i][j] == '1') {14                    width[i][j] = (j == cols - 1) ? 1 : width[i][j + 1] + 1;15                } else {16                    width[i][j] = 0;17                }18            }19        }20 21        int maxArea = 0;22        // Iterate through each cell as a potential top-left corner23        for (int i = 0; i < rows; i++) {24            for (int j = 0; j < cols; j++) {25                int minWidth = Integer.MAX_VALUE;26                // Expand downwards27                for (int k = i; k < rows; k++) {28                    // The width of the rectangle is limited by the narrowest row29                    minWidth = Math.min(minWidth, width[k][j]);30                    if (minWidth == 0) break; // No more rectangle possible31                    int height = k - i + 1;32                    maxArea = Math.max(maxArea, minWidth * height);33                }34            }35        }36        return maxArea;37    }38}