Largest Submatrix With Rearrangements

How it works

We can avoid sorting entirely by maintaining a sorted order implicitly. Track the column indices that had continuous 1s from the previous row. For the current row, first process columns from the previous list (they have taller heights), then add new columns that just started with a 1. This naturally keeps columns ordered by height in descending order.

Steps

1. Maintain a list of column indices from the previous row that had continuous 1s.
2. For each row:
   • Create a new list starting with columns from the previous list that still have a 1 (incrementing their height in the matrix).
   • Append columns where the current cell is 1 but was 0 before (new columns starting at height 1).
   • Compute the maximum area: position i gives area (i + 1) * matrix[r][heights[i]].
3. Return the maximum area.

Complexity

• Time complexity: O(m * n)
• Space complexity: O(n)

Where m is the number of rows and n is the number of columns.

Things to watch for

Resetting Heights on Zero Cells

When building the height array row by row, encountering a 0 should reset the height to 0 for that column. A common mistake is to simply add the previous height regardless of the current cell value, which incorrectly extends heights through 0 cells and produces invalid rectangles.

Forgetting Column Rearrangement is Allowed

Unlike the standard largest rectangle in histogram problem, columns can be rearranged here. Attempting to use a monotonic stack approach without sorting the heights misses the key insight. Sorting heights in descending order allows greedy computation of the maximum area at each width.

Incorrect Area Formula After Sorting

After sorting heights in descending order, the area at position i is (i + 1) * heights[i], not i * heights[i]. The width is the number of columns considered so far (1-indexed), so using i instead of i + 1 underestimates the width by one column.

from typing import List

class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        ROWS, COLS = len(matrix), len(matrix[0])
        res = 0
        prevHeights = []

        for r in range(ROWS):
            heights = []
            for c in prevHeights:
                if matrix[r][c]:
                    matrix[r][c] += matrix[r - 1][c]
                    heights.append(c)

            for c in range(COLS):
                if matrix[r][c] == 1:
                    heights.append(c)

            for i, c in enumerate(heights):
                res = max(res, (i + 1) * matrix[r][c])

            prevHeights = heights

        return res

class Solution {
public:
    int largestSubmatrix(vector<vector<int>>& matrix) {
        int ROWS = matrix.size(), COLS = matrix[0].size(), res = 0;
        vector<int> prevHeights;

        for (int r = 0; r < ROWS; r++) {
            vector<int> heights;

            for (int c : prevHeights) {
                if (matrix[r][c] == 1) {
                    matrix[r][c] += matrix[r - 1][c];
                    heights.push_back(c);
                }
            }

            for (int c = 0; c < COLS; c++) {
                if (matrix[r][c] == 1) {
                    heights.push_back(c);
                }
            }

            for (int i = 0; i < heights.size(); i++) {
                res = max(res, (i + 1) * matrix[r][heights[i]]);
            }

            prevHeights = heights;
        }
        return res;
    }
};