Problem Description

You are given a binary matrix matrix of size m x n (where each element is either 0 or 1). You can rearrange the order of the columns in the matrix in any way you like, but you cannot rearrange the rows or change any values.

After rearranging the columns, your task is to find the area (number of cells) of the largest submatrix consisting entirely of 1's. The submatrix must be rectangular and aligned with the rows and columns of the (possibly rearranged) matrix.

Key constraints:

• You can rearrange columns any way you want, but rows must stay in their original order.
• You can only use 1's in the submatrix; 0's break the rectangle.
• The area is measured as height × width of the submatrix.

Thought Process

At first glance, it may seem like you have to try all possible column orders and check every possible submatrix, but this would be far too slow for large matrices. Instead, let’s look for patterns:

• If we fix a row, we can think about how many consecutive 1's appear in each column "upwards" from that row.
• Rearranging columns allows us to group columns with the most 1's together, maximizing the possible rectangle width for a given height.
• So, for each row, if we know the height of 1's ending at that row in every column, we can sort these heights to simulate the best column arrangement.

This moves us from a brute-force "try every permutation" to a clever way of simulating the best arrangement by sorting the column heights for each row.

Solution Approach

We solve the problem in these steps:

1. Preprocessing: For each cell in the matrix, compute how many consecutive 1's are above it (including itself). This is like building a "histogram" for each row.
2. Simulate Rearrangement: For each row, sort the histogram heights in descending order. The tallest columns can be grouped together after rearrangement.
3. Compute Areas: For each possible width (from 1 to n), the area is height × width, where height is the height of the column at that position in the sorted row.
4. Track Maximum: Keep track of the largest area seen across all rows and widths.

We use sorting for each row to simulate the optimal column arrangement. This is efficient and avoids brute-force permutations.

Example Walkthrough

Suppose matrix = [[0,0,1],[1,1,1],[1,0,1]]:

• Step 1: Build Histogram
  • Row 0: [0, 0, 1]
  • Row 1: [1, 1, 2] (since above are 0, but third column has one more 1 above)
  • Row 2: [2, 0, 3]
• Step 2: Sort Each Row
  • Row 0 sorted: [1, 0, 0]
  • Row 1 sorted: [2, 1, 1]
  • Row 2 sorted: [3, 2, 0]
• Step 3: Compute Area for Each Row
  • Row 0: max(1×1, 0×2, 0×3) = 1
  • Row 1: max(2×1, 1×2, 1×3) = 2
  • Row 2: max(3×1, 2×2, 0×3) = 4
• Step 4: Maximum Area
  • The largest area found is 4.

So, the answer is 4.

Time and Space Complexity

Brute-force approach: Would require checking all permutations of columns (n!) and all possible submatrices, which is not feasible for large n.

Optimized approach:

• Building the histogram: O(mn)
• Sorting each row: O(mn \log n) (since we sort n columns for each of m rows)
• Total time: O(mn \log n)
• Space: O(mn) for the histogram matrix

This is efficient and works well within problem constraints.

Summary

By converting each row into a histogram of consecutive 1's and sorting these heights, we can efficiently simulate the optimal column arrangement to maximize the area of a submatrix of 1's. This approach avoids brute-force permutations and leverages sorting to group the tallest columns together, which is the key insight for this problem.

Code Implementation

class Solution:
    def largestSubmatrix(self, matrix):
        m, n = len(matrix), len(matrix[0])
        heights = [[0]*n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 1:
                    heights[i][j] = heights[i-1][j] + 1 if i > 0 else 1
                else:
                    heights[i][j] = 0
        max_area = 0
        for row in heights:
            sorted_row = sorted(row, reverse=True)
            for k, h in enumerate(sorted_row):
                area = h * (k + 1)
                max_area = max(max_area, area)
        return max_area
      

class Solution {
public:
    int largestSubmatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> heights = matrix;
        for (int i = 1; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (heights[i][j])
                    heights[i][j] += heights[i-1][j];
            }
        }
        int max_area = 0;
        for (int i = 0; i < m; ++i) {
            vector<int> row = heights[i];
            sort(row.rbegin(), row.rend());
            for (int k = 0; k < n; ++k) {
                int area = row[k] * (k + 1);
                max_area = max(max_area, area);
            }
        }
        return max_area;
    }
};
      

class Solution {
    public int largestSubmatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] heights = new int[m][n];
        for (int j = 0; j < n; ++j) {
            heights[0][j] = matrix[0][j];
            for (int i = 1; i < m; ++i) {
                heights[i][j] = matrix[i][j] == 0 ? 0 : heights[i-1][j] + 1;
            }
        }
        int maxArea = 0;
        for (int i = 0; i < m; ++i) {
            int[] row = heights[i].clone();
            Arrays.sort(row);
            for (int k = n - 1; k >= 0; --k) {
                int h = row[k];
                int width = n - k;
                maxArea = Math.max(maxArea, h * width);
            }
        }
        return maxArea;
    }
}
      

var largestSubmatrix = function(matrix) {
    const m = matrix.length, n = matrix[0].length;
    const heights = Array.from({length: m}, () => Array(n).fill(0));
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (matrix[i][j] === 1)
                heights[i][j] = i > 0 ? heights[i-1][j] + 1 : 1;
            else
                heights[i][j] = 0;
        }
    }
    let maxArea = 0;
    for (let i = 0; i < m; ++i) {
        const sortedRow = [...heights[i]].sort((a, b) => b - a);
        for (let k = 0; k < n; ++k) {
            let area = sortedRow[k] * (k + 1);
            if (area > maxArea) maxArea = area;
        }
    }
    return maxArea;
};