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: One optimal rearrangement moves the last column first, then the first column, then the second column:

[
    [1,0,0],
    [1,1,1],
    [1,1,0]
]

The bottom-left 2 x 2 submatrix contains only 1s, so the largest area is 4.

Example 2:

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.

Constraints:

• 1 <= (matrix.length * matrix[i].length) <= 100,000
• matrix[i][j] is either 0 or 1.