LeetCode 1727: Largest Submatrix With Rearrangements

Explanation

To solve this problem, we can use dynamic programming. We will iterate through each row of the matrix and for each row, we will calculate the height of the rectangle of ones that can be formed ending at that row. Then, we will sort the rows in non-increasing order of the heights of the rectangles. Finally, we will calculate the maximum area by considering each column and updating the area if we find a rectangle with ones. The maximum area will be the result.

Algorithm:

1. Iterate through each row of the matrix and for each row, calculate the height of the rectangle of ones that can be formed ending at that row.
2. Sort the rows in non-increasing order of the heights of the rectangles.
3. For each column, update the area if a rectangle of ones can be formed.
4. The maximum area found will be the result.

Time Complexity: O(m * n * log(m)), where m is the number of rows and n is the number of columns in the matrix.

Space Complexity: O(n), where n is the number of columns in the matrix.

class Solution {
    public int largestSubmatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) {
                    matrix[i][j] += matrix[i - 1][j];
                }
            }
        }
        
        int maxArea = 0;
        for (int i = 0; i < m; i++) {
            Arrays.sort(matrix[i]);
            for (int j = 0; j < n; j++) {
                maxArea = Math.max(maxArea, matrix[i][j] * (n - j));
            }
        }
        
        return maxArea;
    }
}