Largest Submatrix With Rearrangements: Sorting Heights Pattern

You are given a binary matrix of size m x n. You can rearrange the columns of the matrix in any order. Return the area of the largest submatrix within the matrix where every element is 1 after reordering the columns optimally.

This is LeetCode 1727: Largest Submatrix With Rearrangements, and it combines the histogram heights trick from "Maximal Rectangle" with a sorting-based greedy that exploits the column rearrangement freedom.

Why this problem matters

Without the rearrangement twist, finding the largest all-ones rectangle in a binary matrix is a classic problem that uses a monotonic stack on histogram heights. But the moment you can reorder columns, the monotonic stack becomes unnecessary. Sorting gives you a cleaner, more direct solution.

This problem teaches you to recognize when a freedom (like rearrangement) simplifies the algorithmic approach rather than complicating it. You will see the same pattern in problems where sorting unlocks a greedy strategy that would otherwise require a more complex data structure.

The key insight

Build consecutive-ones heights per column, just like in "Maximal Rectangle." For each cell (r, c), the height is the number of consecutive 1s ending at row r in column c. If matrix[r][c] is 0, the height resets to 0. Otherwise, it is height[r-1][c] + 1.

Now here is the twist: since you can rearrange columns freely, you sort each row's heights in descending order. After sorting, the tallest columns are on the left. At position i in the sorted row, every column from 0 through i has a height of at least sorted[i]. So the area of the widest rectangle using i + 1 columns at that minimum height is sorted[i] * (i + 1).

You take the maximum across all positions in all rows. That is the answer.

The solution

def largest_submatrix(matrix: list[list[int]]) -> int:
    m, n = len(matrix), len(matrix[0])

    for r in range(1, m):
        for c in range(n):
            if matrix[r][c] == 1:
                matrix[r][c] += matrix[r - 1][c]

    result = 0
    for r in range(m):
        row = sorted(matrix[r], reverse=True)
        for i in range(n):
            if row[i] == 0:
                break
            result = max(result, row[i] * (i + 1))

    return result

The first double loop transforms the matrix in place so that each cell holds its consecutive-ones height. This is the same height computation used in "Maximal Rectangle" and "Largest Rectangle in Histogram."

The second loop processes each row independently. It sorts the heights in descending order, then sweeps left to right. At each index i, row[i] is the shortest bar among the first i + 1 bars (because the array is sorted descending). So row[i] * (i + 1) is the area of the rectangle you can form using those i + 1 columns with row[i] as the limiting height.

The break on row[i] == 0 is a small optimization. Once you hit a zero height in a descending-sorted array, all remaining entries are also zero, so no larger rectangle is possible.

Visual walkthrough

Let's trace through the example matrix step by step. We build heights row by row, sort them, and compute the best rectangle area at each row.

Notice how the sort at each row lets you read off the maximum rectangle directly. You do not need a stack or any complex data structure. The descending order guarantees that the bar at index i is the bottleneck height for a rectangle of width i + 1.

Complexity analysis

Time is O(m * n * log n) where m is the number of rows and n is the number of columns. Building the heights takes O(m * n). For each of the m rows, you sort n values in O(n log n), then scan them in O(n). The sorting dominates, giving O(m * n * log n) overall.

Space is O(n) for the sorted copy of each row. The height computation is done in place on the input matrix, so it requires no extra space beyond the sort buffer.

The building blocks

1. Consecutive-ones column heights

The pattern of transforming a binary matrix into cumulative column heights:

for r in range(1, m):
    for c in range(n):
        if matrix[r][c] == 1:
            matrix[r][c] += matrix[r - 1][c]

This converts each column into a running count of consecutive 1s ending at the current row. A 0 resets the count. You will reuse this exact transformation in "Maximal Rectangle," "Largest Rectangle in Histogram" (applied row by row), and any problem that reduces a 2D binary matrix to a series of histogram problems.

2. Sorted heights greedy area

The pattern of sorting heights and computing area in a single pass:

row = sorted(matrix[r], reverse=True)
for i in range(n):
    if row[i] == 0:
        break
    result = max(result, row[i] * (i + 1))

After sorting descending, row[i] is the minimum height among the first i + 1 bars. The area is row[i] * (i + 1). This greedy scan replaces the monotonic stack you would normally need for histogram problems. It works here because column rearrangement lets you place the tallest bars next to each other. Whenever a problem gives you the freedom to reorder elements, check whether sorting unlocks a simpler greedy approach.

Edge cases

Before submitting, think through these scenarios:

• All zeros: every height is 0. The answer is 0.
• All ones: every height at the last row equals m. Sorted row is all m values. Area = m * n.
• Single row: heights are just the row values (0 or 1). Sorted descending, count the 1s. Area = number of 1s.
• Single column: no sorting effect. Heights build up as consecutive 1s. Area = longest consecutive run of 1s.
• Zeros scattered in every row: heights reset frequently. Each row's sorted heights may be short, so the answer is small.
• One column of all 1s, rest mixed: that column reaches height m, but sorted with others it may not help much. The scan at each row checks all widths.

From understanding to recall

You have seen how consecutive-ones heights plus a descending sort gives you the largest rearranged submatrix in a clean two-pass solution. The logic is short and the idea is elegant: sorting replaces the monotonic stack because column reordering is free.

The details that trip people up in interviews are the height update (do you add to the cell above or replace it?) and the area formula (is it row[i] * i or row[i] * (i + 1)?). These are off-by-one traps, and they cost time under pressure.

Spaced repetition is how you eliminate them. You practice writing the height transformation and the sorted greedy scan from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "rearrange columns to maximize rectangle" and the two-pass solution flows out without hesitation.

Related posts

• Largest Rectangle in Histogram - The monotonic stack approach for fixed-order histograms, which this problem bypasses with sorting
• Maximal Rectangle - The same column height trick applied without column rearrangement, requiring a stack per row
• Maximal Square - A simpler DP variant that finds the largest all-ones square instead of rectangle

CodeBricks breaks Largest Submatrix With Rearrangements into its column height transformation and sorted greedy scan building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a matrix problem shows up in your interview, you do not think about it. You just write it.