Largest Submatrix With Rearrangements - Solution & Explanation
Problem Statement
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.
Approach Overview
Problem Overview: You are given a binary matrix. Columns can be rearranged independently for each row. The goal is to maximize the area of a submatrix consisting entirely of 1s after rearranging columns. The challenge is recognizing that column order doesn't matter per row—only the heights of consecutive 1s matter.
Approach 1: Column Height Calculation and Sorting (O(m * n log n) time, O(n) space)
Convert the matrix into heights of consecutive 1s for each column. Iterate row by row; if matrix[r][c] == 1, add the value from the row above, otherwise reset to 0. This transforms each row into a histogram of heights. Since columns can be rearranged, sort the heights of the current row in descending order. Then compute candidate areas using height[i] * (i + 1), where i + 1 represents how many columns you keep after sorting. The key insight: rearranging columns lets you group the tallest columns together, maximizing width for large heights. This greedy idea combined with sorting produces the optimal area for each row.
While scanning rows, keep a running maximum area. Each row effectively becomes the base of a potential rectangle where height comes from consecutive 1s above it and width comes from selecting the tallest columns after sorting. Time complexity is dominated by sorting each row: O(m * n log n). Space complexity stays O(n) if you reuse the row array.
Approach 2: Histogram-Based Greedy Strategy (O(m * n log n) time, O(n) space)
This approach frames the same idea using a histogram perspective similar to classic rectangle problems. For each row, maintain a height array where height[c] counts consecutive 1s ending at that row. Instead of preserving original column order, copy the height array and sort it in descending order. Treat the sorted histogram as if columns were rearranged optimally. Iterate through the sorted heights and compute areas using height[i] * (i + 1). The reasoning relies on a greedy observation: if you want a rectangle of width w, you should pick the w tallest columns.
This histogram interpretation clarifies why rearranging columns works. Any rectangle formed after rearrangement corresponds to choosing a subset of columns whose minimum height determines the rectangle height. Sorting exposes these candidates quickly. Complexity remains O(m * n log n) due to sorting per row.
Recommended for interviews: The column height + sorting method is the standard expectation. Interviewers want to see two insights: converting the matrix into vertical heights and recognizing that column rearrangement allows sorting each row. Explaining the brute reasoning first—"group tallest columns to maximize width"—shows understanding, while implementing the sorted height calculation demonstrates strong array and matrix manipulation skills.
Approach 1: Column Height Calculation and Sorting
This approach involves calculating column heights for each row and optimizing with column-wise rearrangements.
The idea is to calculate how many consecutive 1s appear in each column up to the current row. Then, for each row, we sort these heights to maximize the formation of the largest possible rectangle that can be formed with a base equal to the height of each column. The largest rectangle area for each row is calculated by iterating over the sorted heights and using them as potential heights for the rectangle base, multiplying by the number of consecutive columns with at least this height.
In the Python solution, we first calculate the heights of consecutive 1s for each cell in the matrix. We create a heights matrix that accumulates the heights of each column. Then, for each row, we sort these heights in descending order. We then iterate over the sorted heights to compute the maximum area possible by treating each height as forming a rectangle with a base of the number of columns that can extend this height.
Complexity
Time Complexity: O(m * n log n), where m is the number of rows and n is the number of columns. This is because for each row we do a sort operation.
Space Complexity: O(m * n) for the heights matrix and additional space for sorting.
Approach 2: Histogram Approach
This approach treats each row as a base of a histogram. It calculates heights for consecutive 1s for each column, row-by-row. The optimal area is found by considering each row as a base and calculating the maximum rectangular area for each.
In the JavaScript solution, we calculate the heights of consecutive 1s for each column in a similar manner to the Python approach. We store these heights in a 2D array and sort each row in descending order to maximize rectangle height for calculations.
Code
JavaScript
C#
Complexity
Time Complexity: O(m * n log n) due to sorting operations.
Space Complexity: O(m * n) for storing the heights.
Approach 3: 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 geq 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 times k. We iterate through the elements of the row from largest to smallest, take the maximum value of 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.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Column Height Calculation and Sorting | Time Complexity: O(m * n log n), where m is the number of rows and n is the number of columns. This is because for each row we do a sort operation. |
| Histogram Approach | Time Complexity: O(m * n log n) due to sorting operations. |
| Preprocessing + Sorting | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Column Height Calculation and Sorting | O(m * n log n) | O(n) | General optimal approach; clear logic and commonly expected in interviews |
| Histogram Greedy Strategy | O(m * n log n) | O(n) | When reasoning about rectangles using histogram intuition |
| Counting Sort Optimization | O(m * n) | O(m) | When height values are bounded by row count and you want to remove sorting overhead |
Video Solution
Largest Submatrix With Rearrangements | Build Intuition | 3 Approaches | Leetcode 1727 | MIK • codestorywithMIK • 12,522 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Largest Submatrix With Rearrangements easy or hard?
Largest Submatrix With Rearrangements Python/Java solution
How to solve Largest Submatrix With Rearrangements in O(n)?
What is the best approach for Largest Submatrix With Rearrangements?
Is Largest Submatrix With Rearrangements asked at Google/Amazon/Meta?
What data structure is used in Largest Submatrix With Rearrangements?
What is the time complexity of Largest Submatrix With Rearrangements?
Ready to solve this problem?
Practice Largest Submatrix With Rearrangements with our built-in code editor and test cases.
Practice on FleetCode