1727. Largest Submatrix With Rearrangements

not modify input

T: O(m*(n+nlogn+n)
S: O(n + n)

```java
class Solution {
    public int largestSubmatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int result = 0;
        int[] maxHeight = new int[n]; // for each col, max height can be.. ?  (from height to x, all 1 is the max height)
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    maxHeight[j] = 0; // once there is a 0 in this row's any col, reset height to 0
                } else {
                    maxHeight[j] += 1;
                }
            }

            // for each row, we all need to cal max area, because sometimes ans is in part area
            int[] newHeight = Arrays.copyOf(maxHeight, maxHeight.length);
            Arrays.sort(newHeight); 
            // sort it! like rearrage, so height is ascending, for calculating max area, 小的高會限制大的, 所以小的高排前面 

            for (int j = 0; j < n; j++) { 
                result = Math.max(result, newHeight[j]*(n-j)); // cal max area: heigh*width
            }
        }
        return result;
    }
}

/***
not modify input

refer to 
https://leetcode.com/problems/largest-submatrix-with-rearrangements/solutions/1020710/c-clean-and-clear-with-intuitive-pictures-o-m-n-logn/?envType=daily-question&envId=2023-11-26

T: O(m*(n+nlogn+n)
S: O(n + n)

 */
```

modify input

```java
class Solution {
    public int largestSubmatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int result = 0;
        
        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]+1;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            Arrays.sort(matrix[i]);
            for (int j = 0; j < n; j++) { 
                result = Math.max(result, matrix[i][j]*(n-j)); // cal max area: heigh*width
            }
        }
        return result;
    }
}

/***
modify input

combine  
https://leetcode.com/problems/largest-submatrix-with-rearrangements/solutions/1020710/c-clean-and-clear-with-intuitive-pictures-o-m-n-logn/?envType=daily-question&envId=2023-11-26

and
https://leetcode.com/problems/largest-submatrix-with-rearrangements/solutions/1020682/java-6ms-easy-understanding-with-comments-and-images/?envType=daily-question&envId=2023-11-26

ex:
Input: matrix = [[0,0,1],[1,1,1],[1,0,1]]
Output: 4
[
    [0,0,1],
    [1,1,1],
    [1,0,1]]
->
cal height
0 0 1
1 1 2
2 0 3
then row by row and sort it, to cal max area

0 0 1 -> max area:1

1 1 2 -> max(1*3, 1*2, 2*1) = 3

2 0 3 ->sort -> 0 2 3 -> max(0*3, 2*2, 3*1) = 4
so ans is max(1,3,4) = 4

T: O(m*n + m*(nlogn+n))
S: O(1)

 */
```