Watch 10 video solutions for Largest Submatrix With Rearrangements, a medium level problem involving Array, Greedy, Sorting. This walkthrough by codestorywithMIK has 12,147 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.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 | 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 |