Description
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 either 0 or 1.
Solutions
Solution 1: Preprocessing + Sorting
Since the matrix can be rearranged by columns, we can preprocess each column of the matrix first.
For each element with value 1, we update its value to the maximum number of consecutive 1s above it (including itself), i.e., matrix[i][j] = matrix[i-1][j] + 1.
Next, we sort each row of the updated matrix. Then we traverse each row and compute the maximum area of an all-1 submatrix with that row as the bottom edge. The detailed calculation is as follows:
For a given row, let the k-th largest element be val_k, where k ≥ 1. Then there are at least k elements in that row no less than val_k, forming an all-1 submatrix with area val_k × k. We iterate through the elements of the row from largest to smallest, take the maximum value of val_k × k, and update the answer.
The time complexity is O(m × n × log n) and the space complexity is O(log n), where m and n are the number of rows and columns of the matrix, respectively.
PythonJavaC++GoTypeScriptRustC#
class Solution:
def largestSubmatrix(self, matrix: List[List[int]]) -> int:
for i in range(1, len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j]:
matrix[i][j] = matrix[i - 1][j] + 1
ans = 0
for row in matrix:
row.sort(reverse=True)
for j, v in enumerate(row, 1):
ans = max(ans, j * v)
return ans(code-box)
class Solution {
public int largestSubmatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
for (int i = 1; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 1) {
matrix[i][j] = matrix[i - 1][j] + 1;
}
}
}
int ans = 0;
for (var row : matrix) {
Arrays.sort(row);
for (int j = n - 1, k = 1; j >= 0 && row[j] > 0; --j, ++k) {
int s = row[j] * k;
ans = Math.max(ans, s);
}
}
return ans;
}
}(code-box)
class Solution {
public:
int largestSubmatrix(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
for (int i = 1; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j]) {
matrix[i][j] = matrix[i - 1][j] + 1;
}
}
}
int ans = 0;
for (auto& row : matrix) {
sort(row.rbegin(), row.rend());
for (int j = 0; j < n; ++j) {
ans = max(ans, (j + 1) * row[j]);
}
}
return ans;
}
};(code-box)
func largestSubmatrix(matrix [][]int) int {
m, n := len(matrix), len(matrix[0])
for i := 1; i < m; i++ {
for j := 0; j < n; j++ {
if matrix[i][j] == 1 {
matrix[i][j] = matrix[i-1][j] + 1
}
}
}
ans := 0
for _, row := range matrix {
sort.Ints(row)
for j, k := n-1, 1; j >= 0 && row[j] > 0; j, k = j-1, k+1 {
ans = max(ans, row[j]*k)
}
}
return ans
}(code-box)
function largestSubmatrix(matrix: number[][]): number {
const m: number = matrix.length;
const n: number = matrix[0].length;
for (let i: number = 1; i < m; ++i) {
for (let j: number = 0; j < n; ++j) {
if (matrix[i][j] !== 0) {
matrix[i][j] = matrix[i - 1][j] + 1;
}
}
}
let ans: number = 0;
for (const row of matrix) {
row.sort((a, b) => b - a);
for (let j: number = 0; j < n; ++j) {
ans = Math.max(ans, (j + 1) * row[j]);
}
}
return ans;
}(code-box)
impl Solution {
pub fn largest_submatrix(mut matrix: Vec<Vec<i32>>) -> i32 {
let m: usize = matrix.len();
let n: usize = matrix[0].len();
for i in 1..m {
for j in 0..n {
if matrix[i][j] != 0 {
matrix[i][j] = matrix[i - 1][j] + 1;
}
}
}
let mut ans: i32 = 0;
for row in matrix.iter_mut() {
row.sort_unstable_by(|a, b| b.cmp(a));
for j in 0..n {
ans = ans.max((j as i32 + 1) * row[j]);
}
}
ans
}
}(code-box)
public class Solution {
public int LargestSubmatrix(int[][] matrix) {
int m = matrix.Length;
int n = matrix[0].Length;
for (int i = 1; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] != 0) {
matrix[i][j] = matrix[i - 1][j] + 1;
}
}
}
int ans = 0;
foreach (var row in matrix) {
Array.Sort(row);
Array.Reverse(row);
for (int j = 0; j < n; ++j) {
ans = Math.Max(ans, (j + 1) * row[j]);
}
}
return ans;
}
}(code-box)
