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.The key idea in #1727 Largest Submatrix With Rearrangements is to treat each row as the base of a histogram. First, compute the height of consecutive 1s for every column by accumulating values from the rows above. This transforms the matrix into a set of histogram heights representing how tall a column of ones can extend upward.
Since columns in each row can be rearranged, we can sort the column heights in descending order for that row. After sorting, evaluate possible submatrix areas by considering the width formed by the first k columns and the minimum height among them. The area becomes height[k] * (k + 1). Repeating this for every row ensures we capture the largest possible rectangle formed after rearranging columns.
This approach combines greedy reasoning and sorting to maximize area at each row level. The overall time complexity is typically O(m * n log n) due to sorting each row, with O(1) or O(m * n) additional space depending on how heights are stored.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Histogram Heights + Row Sorting | O(m * n log n) | O(1) extra or O(m * n) depending on implementation |
| Optimized Counting / Frequency Method | O(m * n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
For each column, find the number of consecutive ones ending at each position.
For each row, sort the cumulative ones in non-increasing order and "fit" the largest submatrix.
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.
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.
1import java.util.Arrays;
2
3public class Solution {
4 public int largestSubmatrix(int[][] matrix) {
5 int m = matrix.length, n = matrix[0].length;
6 int[][] heights = new int[m][n];
7
8 // Compute heights column by column
9 for (int j = 0; j < n; j++) {
10 for (int i = 0; i < m; i++) {
11 if (matrix[i][j] == 1) {
12 heights[i][j] = (i == 0) ? 1 : heights[i - 1][j] + 1;
13 }
14 }
15 }
16
17 int maxArea = 0;
18 for (int i = 0; i < m; i++) {
19 Arrays.sort(heights[i]); // Sort each row
20 for (int j = n - 1; j >= 0; j--) {
21 maxArea = Math.max(maxArea, heights[i][j] * (n - j));
22 }
23 }
24
25 return maxArea;
26 }
27}In this Java solution, we use a similar approach to the Python code. We calculate the heights array where each element represents the maximum height of continuous 1s for each column in the matrix up to that row. We then sort each row of the heights array in descending order and calculate the maximum rectangle area by iterating through the sorted heights.
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.
Time Complexity: O(m * n log n) due to sorting operations.
Space Complexity: O(m * n) for storing the heights.
1function largestSubmatrix(matrix) {
2 if
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Sorting allows us to simulate rearranging columns so that taller columns are grouped together. This maximizes the potential width for larger heights, helping compute the maximum possible submatrix area for each row.
Yes, problems involving matrix transformations, greedy strategies, and histogram-based reasoning are common in FAANG-style interviews. This question tests understanding of matrix preprocessing, sorting, and area optimization.
Arrays are the primary data structure used to track the height of consecutive ones in each column. Sorting these arrays for each row helps simulate column rearrangements and evaluate possible submatrix widths.
The optimal approach converts each row into histogram heights of consecutive 1s. For every row, sort the column heights in descending order and compute the possible rectangle areas using width and height combinations. This greedy strategy ensures the largest valid submatrix is found efficiently.
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.