#1727
Largest Submatrix With Rearrangements
pupil · 495 · lc medium +27 · verified · 75.2% accepted · 1,978 likes · top 86%
Description
You are given a binary matrix matrix of size m x n. You may reorder the columns in any order. Return the area of the largest all-ones submatrix achievable after an optimal column rearrangement.
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.
Code
1
2
3