1727. Largest Submatrix With Rearrangements

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.length
n == matrix[i].length
1 <= m * n <= 10⁵
matrix[i][j] is either 0 or 1.

Solutions

Solution 1: Preprocessing + Sorting

Thinking

Columns may be reordered; we want the largest all-ones submatrix. \(m\cdot n\le 10^5\) forbids trying permutations.

Reordering changes column order, not the upward run of ones in a column. After rewriting each \(1\) as that height, a row is a histogram.

Sort the row descending. The \(k\)-th largest height \(v\) forms a \(v\times k\) all-ones block. Take the maximum over rows.

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 \(1\)s above it (including itself), i.e., \(\text{matrix}[i][j] = \text{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 \(\text{val}_k\), where \(k \geq 1\). Then there are at least \(k\) elements in that row no less than \(\text{val}_k\), forming an all-\(1\) submatrix with area \(\text{val}_k \times k\). We iterate through the elements of the row from largest to smallest, take the maximum value of \(\text{val}_k \times k\), and update the answer.

The time complexity is \(O(m \times n \times \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.

Python3JavaC++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

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;
    }
}

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;
    }
};

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
}

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;
}

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
    }
}

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;
    }
}

1727. Largest Submatrix With Rearrangements

Description

Solutions

Solution 1: Preprocessing + Sorting

Comments