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.

&nbsp;
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.


&nbsp;
Constraints:


	m == matrix.length
	n == matrix[i].length
	1 &lt;= m * n &lt;= 105
	matrix[i][j] is either 0 or 1.


from collections import Counter

class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        M = len(matrix)
        N = len(matrix[0])

        colcons = [] # preprocess columns
        for c in range(N):
            cons = []
            s = 0
            for r in range(M):
                if not matrix[r][c]:
                    s = 0
                else:
                    s += 1
                cons.append(s)
            colcons.append(cons)
        # colcons[c][r] is how much 1's we'll get if we start from column c at row r and go up

        best = 0
        for r in range(M):
            # try r as the lowest row
            C = Counter(colcons[c][r] for c in range(N))
            vs = sorted(C.keys(), reverse=True)
            cs = accumulate(C[v] for v in vs)
            for v,c in zip(vs,cs):
                best = max(best,v*c)
        return best
class Solution {
    public int largestSubmatrix(int[][] matrix) {
         //Store matrix[i][j]= total number of consecutive 1s along column j ending at index (i,j).
        for(int i=1;i<matrix.length;i++)  //Start from row 1 because row 0 will be unaffected as no row above it.
        {
            for(int j=0;j<matrix[i].length;j++)
            {
                if(matrix[i][j]==0) continue;
                else  matrix[i][j]=matrix[i-1][j]+1;
            }
        }
        
        int maxSize=0;
        for(int i=0;i<matrix.length;i++)
        {
           
            PriorityQueue<Integer> pq  =  new PriorityQueue<Integer>();// minheap
            for(int j=0;j<matrix[i].length;j++)
            {
                if(matrix[i][j]>0)  pq.add(matrix[i][j]); // Add all the entries from row i in minheap
            }
            int size=0,curr=0;
            /*
                In current row, total entries with value k or greater than k will contribute the squares of
				size=k*(number of squares of size k or greater than k).Largest square ending at current
				row= k * (all entries greater than or equal to k in current row) for all ks in current row
            */
            while(!pq.isEmpty())  
            {
                curr=pq.peek(); 
                
                size=curr*pq.size();
                maxSize=Math.max(maxSize,size);
                
                pq.poll();
            }
        }
        return maxSize;
        
        
        
    }
}
class Solution {
public:
    int largestSubmatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        int ans = 0;
        vector<int> height(n, 0);
		
		// view each row and its above as pillars 
        for(int i = 0; i < m; ++i){
			// calculate heights
            for(int j = 0; j < n; ++j){
                if(matrix[i][j] == 0) height[j] = 0;
                else height[j] += 1;
            }
			
			// sort pillars
            vector<int> order_height = height;
            sort(order_height.begin(), order_height.end());
			
			// iterate to get the maxium rectangle
            for(int j = 0; j < n; ++j){
                ans = max(ans, order_height[j] * (n - j));
            }
        }
        return ans;
    }
};
var largestSubmatrix = function(matrix) {
    let n = matrix.length;
    let m = matrix[0].length;
    let col = new Array(m).fill(0);
    let res = 0;
    for(let i = 0; i < n; i++){
        for(let j = 0; j < m; j++){
            if(matrix[i][j]) col[j]++;
            else col[j] = 0;
        }
        res = counting(col, res);
    }
    return res;
};


//if you did 84. Largest Rectangle in Histogram, you can replace the following part with your 84 answer and don't forget to sort.
let counting = function(column, max) {
     let sorted = [...column].sort((a,b)=>b-a);
     let k, j;
    for (let i=0; i < sorted.length ;i++){
        if(sorted[i]===sorted[i-1]) continue;  
        k = j = i;
        while(sorted[j]&&sorted[j]>=sorted[i]) j++;
        while(sorted[k]&&sorted[k]>=sorted[i]) k--;
        max = Math.max(sorted[i]*Math.abs(k-j+1), max);
    }
    return max;
};
Largest Submatrix With Rearrangements