1727. 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.
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m * n <= 105matrix[i][j]is either0or1.
GoogleTopics
Hints open one at a time
Hint 1
For each column, find the number of consecutive ones ending at each position.
Hint 2
For each row, sort the cumulative ones in non-increasing order and "fit" the largest submatrix.
Similar problems
Max Area of IslandMediumLoading editor…
1class Solution:
2 def largestSubmatrix(self, matrix: List[List[int]]) -> int:
3
Starter codePython 3Spaces: 4
Loading editor…
1class Solution:
2 def largestSubmatrix(self, matrix: List[List[int]]) -> int:
3
Starter codePython 3Spaces: 4
Examples
Input
[[0,0,1],[1,1,1],[1,0,1]]
Input
[[1,0,1,0,1]]
Input
[[1,1,0],[1,0,1]]
Your code is saved on this device.Solution