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.
This approach improves upon brute-force by realizing that for any submatrix of ones, its columns can be rearranged to be contiguous. This means for any given row, we can find the maximum area of a rectangle of ones ending at that row by considering the heights of consecutive ones above each cell. The key insight is that rearranging columns is equivalent to rearranging the heights. However, this version calculates these heights inefficiently.
Algorithm
- Initialize
maxArea = 0. - Iterate through each row
ifrom0tom-1. This row will be the base of potential rectangles. - For the current row
i, create aheightsarray of sizen. - For each column
jfrom0ton-1:- Calculate
heights[j]by counting consecutive1s upwards frommatrix[i][j]. This involves a loop from rowiup to0.
- Calculate
- Once the
heightsarray for rowiis computed, sort it in ascending order. - Iterate through the sorted heights. For each height
hat indexk, it can form a rectangle of areah * (n-k). - Update
maxAreawith the maximum area found. - After checking all rows, return
maxArea.
Walkthrough
For each row i, we treat it as the bottom edge of a potential submatrix. For each column j, we determine the height of the pillar of 1s ending at (i, j) by scanning upwards. This gives us a histogram for row i. Since columns can be rearranged, we can sort these heights. A height h can be the height of a rectangle if we group it with all other columns that have a height of at least h. By sorting the heights, say h_1 <= h_2 <= ... <= h_n, the rectangle with height h_k can have a width of n-k+1. The inefficiency comes from the O(m) work to find the height for each of the n cells in a row.
import java.util.Arrays; class Solution { public int largestSubmatrix(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; int maxArea = 0; for (int i = 0; i < m; i++) { int[] heights = new int[n]; for (int j = 0; j < n; j++) { if (matrix[i][j] == 1) { // Inefficiently calculate height by looking up int h = 0; for (int k = i; k >= 0; k--) { if (matrix[k][j] == 1) { h++; } else { break; } } heights[j] = h; } } Arrays.sort(heights); for (int j = 0; j < n; j++) { int height = heights[j]; int width = n - j; maxArea = Math.max(maxArea, height * width); } } return maxArea; }}Complexity
Time
O(m^2 * n). For each of the `m` rows, calculating heights for `n` columns takes `O(m*n)`. Sorting takes `O(n log n)`. The total time is `O(m * (m*n + n log n))`, which is dominated by `O(m^2 * n)`.
Space
O(n) to store the `heights` array for each row.
Trade-offs
Pros
A significant improvement over the factorial complexity of brute-force.
Correctly identifies the core subproblem of processing row by row.
Cons
Inefficiently recalculates heights from scratch for every row, leading to a high polynomial time complexity.
Performs much redundant work.
This is an efficient and practical approach that uses dynamic programming to optimize the calculation of heights. Instead of re-calculating the height of consecutive 1s for each cell from scratch, it builds upon the heights from the previous row. For each row, it computes the heights, sorts them, and then calculates the maximum possible rectangle area, leveraging the fact that columns can be reordered.
Algorithm
- The core idea is to process the matrix row by row, maintaining the height of consecutive
1s ending at each cell. - Use the matrix itself or an auxiliary 1D array
heightsto store these heights dynamically. - Iterate through each row
ifrom0tom-1:- Update the
heightsfor the current row. For each columnj:- If
matrix[i][j] == 1, the new height is the previous height for that column plus one. - If
matrix[i][j] == 0, the height resets to0.
- If
- After computing the heights for the current row, treat them as bars of a histogram.
- Since we can rearrange columns, we can sort these heights to find the optimal arrangement.
- Create a copy of the current
heightsarray and sort it in ascending order. - Iterate through the sorted heights. A height
hat indexkcan form a rectangle of areah * (n-k). - Update a global
maxAreavariable with the largest area found.
- Update the
- Return
maxArea.
Walkthrough
We can transform the input matrix into a matrix of heights. For each cell (i, j), matrix[i][j] will store the number of consecutive 1s ending at this cell, looking upwards. This is done with a single pass. matrix[i][j] = matrix[i-1][j] + 1 if matrix[i][j] == 1. After this preprocessing for a row, that row represents a histogram. Since we can rearrange columns, we can sort the histogram bars (heights). If we sort the heights for a row in ascending order, h_0, h_1, ..., h_{n-1}, then for any height h_j, we know there are n-j columns with height at least h_j. Thus, we can form a rectangle of height h_j and width n-j. We find the maximum of h_j * (n-j) over all j for each row and take the overall maximum.
import java.util.Arrays; class Solution { public int largestSubmatrix(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; int maxArea = 0; // We can use a separate heights array or modify the matrix in-place. // Here, we modify the matrix to store heights. 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]; } } } // For each row, sort the heights and calculate the max area. for (int i = 0; i < m; i++) { // Create a copy of the row to sort, as sorting modifies the array. int[] currentRow = Arrays.copyOf(matrix[i], n); Arrays.sort(currentRow); for (int j = 0; j < n; j++) { int height = currentRow[j]; // The width is the number of columns with height >= current height. // Since the array is sorted, there are (n - j) such columns. int width = n - j; maxArea = Math.max(maxArea, height * width); } } return maxArea; }}Complexity
Time
O(m * n log n). The height calculation across all rows takes `O(m*n)`. Then, for each of the `m` rows, we sort an array of size `n`, which takes `O(n log n)`. The total time is dominated by the sorting step across all rows.
Space
O(n). If modifying the input matrix is allowed, we still need `O(n)` space to create a copy of each row for sorting. If not, `O(m*n)` would be needed for a separate heights matrix, but a row-by-row approach with an `O(n)` heights array is also possible and optimal.
Trade-offs
Pros
Efficiently calculates heights using dynamic programming in
O(m*n).Provides a robust and generally fast solution with
O(m * n log n)complexity.Simple to implement and understand.
Cons
The
log nfactor from sorting might be suboptimal for matrices that are very wide and not tall, where a counting sort based approach (O(m*(n+m))) could be faster.
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; }}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; }};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 ansVideo 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.