# Largest Submatrix With Rearrangements
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/largest-submatrix-with-rearrangements)
Canonical: https://scaleengineer.com/dsa/problems/largest-submatrix-with-rearrangements
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Matrix
**Companies:** [Samsung](https://scaleengineer.com/companies/samsung), [Directi](https://scaleengineer.com/companies/directi)
---
## Problem
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:**

![](https://assets.glich.co/dsa/largest-submatrix-with-rearrangements/image0.png) 

**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:**

![](https://assets.glich.co/dsa/largest-submatrix-with-rearrangements/image1.png) 

**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.length`
* `n == matrix[i].length`
* `1 <= m * n <= 105`
* `matrix[i][j]` is either `0` or `1`.

# Approaches
## Brute-Force with Column Permutations
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.
**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.
**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.
### Explanation
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.

```java
// 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
    }
}
```
### 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.

## Naive Row-by-Row Processing
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.
**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.
**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.
### Explanation
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 `1`s 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.

```java
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;
    }
}
```
### Algorithm
- Initialize `maxArea = 0`.
- Iterate through each row `i` from `0` to `m-1`. This row will be the base of potential rectangles.
- For the current row `i`, create a `heights` array of size `n`.
- For each column `j` from `0` to `n-1`:
  - Calculate `heights[j]` by counting consecutive `1`s upwards from `matrix[i][j]`. This involves a loop from row `i` up to `0`.
- Once the `heights` array for row `i` is computed, sort it in ascending order.
- Iterate through the sorted heights. For each height `h` at index `k`, it can form a rectangle of area `h * (n-k)`.
- Update `maxArea` with the maximum area found.
- After checking all rows, return `maxArea`.

## DP for Heights + Sorting
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 `1`s 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.
**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.
**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 n` factor 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.
### Explanation
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 `1`s 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.

```java
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;
    }
}
```
### Algorithm
- The core idea is to process the matrix row by row, maintaining the height of consecutive `1`s ending at each cell.
- Use the matrix itself or an auxiliary 1D array `heights` to store these heights dynamically.
- Iterate through each row `i` from `0` to `m-1`:
  - Update the `heights` for the current row. For each column `j`:
    - 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 to `0`.
  - 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 `heights` array and sort it in ascending order.
  - Iterate through the sorted heights. A height `h` at index `k` can form a rectangle of area `h * (n-k)`.
  - Update a global `maxArea` variable with the largest area found.
- Return `maxArea`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```