Largest Submatrix With Rearrangements

You are given a binary matrix matrix of size m x n, and you are allowed to rearrange the columns of the matrix in any order.

Return the area of the largest submatrix within matrix where every element of the submatrix is 1 after reordering the columns optimally.

 

Example 1:

Input: matrix = [[0,0,1],[1,1,1],[1,0,1]]
Output: 4
Explanation: You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 4.
Example 2:

Input: matrix = [[1,0,1,0,1]]
Output: 3
Explanation: You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 3.
Example 3:

Input: matrix = [[1,1,0],[1,0,1]]
Output: 2
Explanation: Notice that you must rearrange entire columns, and there is no way to make a submatrix of 1s larger than an area of 2.
Example 4:

Input: matrix = [[0,0],[0,0]]
Output: 0
Explanation: As there are no 1s, no submatrix of 1s can be formed and the area is 0.
 

Constraints:


Solution:

start from row 1, calculate the heights for row0, row0 - 1, row 0 -2, and sort the heights, then calculate the largest rectangle possible

First think of what we can do with a collection of histograms ? What is the largest rectangle we can form?



Unlike 84. Largest Rectangle in Histogram, the pillar in this question can be rearranged !



Feel better now? Yes, for each pillar it can centainly form a rectangle with it's right neighbors.

So we just iterate every pillar and calculate the maximum rectangle.


Now comes the tricky part for this question, we can view each row with its above as a collection of pillars!
And if the matrix[row][col] is 1 , we add the height of pillar in col by 1, height[row][col] = height[row - 1][col] + 1,
else if matrix[row][col] is 0, we reset the height of pillar in col as 0, height[row][col] = 0, because we can see it as broken pillar and hence useless.


Example



class Solution {
    public int largestSubmatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int max = 0;
        int[] heights = new int[n];
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                if (i == 0) {
                    heights[j] += matrix[i][j];
                } else if (matrix[i][j] == 0) {
                    heights[j] = 0;
                } else {
                    heights[j] ++;
                }
            }
            
            int[] sorted = heights.clone();
            Arrays.sort(sorted);
            // System.out.println(Arrays.toString(sorted));

            for (int j = 0; j < n; j ++) {
                max = Math.max(max, sorted[j] * (n - j));
            }
        }
        return max;
    }
}