Largest Submatrix With Rearrangements
MedPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly tackles the problem by exploring every possible arrangement of columns. For each arrangement, it then solves the standard problem of finding the largest submatrix of ones in a fixed matrix. While correct, the number of column permutations grows factorially, making this method infeasible.
Algorithm
- Generate all
n!permutations of the column indices[0, 1, ..., n-1]. - For each permutation:
- Construct a new matrix by rearranging the columns of the original matrix according to the current permutation.
- In this new matrix, find the largest rectangle of all ones. This subproblem can be solved in
O(m*n)time, for example, by using the "Largest Rectangle in Histogram" algorithm for each row. - Keep track of the maximum area found across all permutations.
- Return the overall maximum area.
Walkthrough
The core idea is to exhaustively check every configuration. You would need a function to generate the next permutation of columns, apply it to the matrix, and then run a standard algorithm to find the largest all-one rectangle within that specific configuration. The complexity of this sub-problem is already significant, and repeating it for n! configurations leads to an astronomical total runtime.
// This is a conceptual illustration. A full implementation is impractical.class Solution { public int largestSubmatrix(int[][] matrix) { // This approach is too slow and will time out (TLE). // It's for conceptual understanding only. int m = matrix.length; int n = matrix[0].length; int[] cols = new int[n]; for (int i = 0; i < n; i++) { cols[i] = i; } int maxArea = 0; // Generate all permutations of column indices do { int[][] permutedMatrix = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { permutedMatrix[i][j] = matrix[i][cols[j]]; } } maxArea = Math.max(maxArea, largestRectangleOfOnes(permutedMatrix)); } while (nextPermutation(cols)); return maxArea; } // Helper to find largest rectangle of ones in a fixed matrix (O(m*n)) private int largestRectangleOfOnes(int[][] M) { // ... implementation of largest rectangle in histogram for each row ... return 0; // Placeholder } // Helper to generate next permutation private boolean nextPermutation(int[] nums) { // ... implementation of next permutation algorithm ... return false; // Placeholder }}Complexity
Time
O(n! * m * n). Generating all `n!` permutations and for each, solving the largest rectangle subproblem in `O(m*n)` time.
Space
O(m * n) to store the permuted matrix for each permutation.
Trade-offs
Pros
Conceptually straightforward as it directly models the problem statement.
Cons
Extremely high time complexity, making it impractical for all but the smallest inputs.
Requires significant memory to store the permuted matrix.
Solutions
Solution
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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.