LeetCode 1727 - Largest Submatrix With Rearrangements

LeetCode Problem 1727

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting, Matrix

Solution

Problem Understanding

The problem gives us a binary matrix, meaning every cell contains either 0 or 1. We are allowed to rearrange the columns of the matrix in any order we want. The rearrangement is global for the row configuration being considered, meaning we are effectively free to permute the columns to maximize the size of a rectangular submatrix consisting entirely of 1s.

The important detail is that we are not changing the values inside a column. We are only changing the order of columns. This means the vertical continuity of 1s inside each column remains unchanged.

The goal is to compute the largest possible rectangular area made entirely of 1s after optimally rearranging the columns.

The input is:

• matrix, an m x n binary matrix
• m is the number of rows
• n is the number of columns

The output is:

• The maximum area of a submatrix consisting entirely of 1s after rearranging columns optimally

The constraints are important:

• 1 <= m * n <= 10^5

This immediately tells us that quadratic or cubic solutions over all cells will likely be too slow. We need something close to linear or O(m * n log n).

A naive approach might attempt every column permutation, but there are n! possible permutations, which becomes impossible very quickly.

There are several important observations and edge cases:

• A row may contain all zeros, which contributes nothing.
• A matrix may contain all ones, in which case the answer is the full matrix area.
• A single row matrix reduces to counting the maximum number of 1s after rearrangement.
• A single column matrix reduces to finding the tallest consecutive vertical segment of 1s.
• The optimal rectangle may end at any row, not necessarily the last row.
• Rearranging columns independently for each row is effectively allowed for maximizing the rectangle ending at that row, because only the heights matter.

The key challenge is determining how to efficiently evaluate the best rectangle after reordering columns.

Approaches

Brute Force Approach

A brute force strategy would attempt to generate different column permutations and then compute the largest rectangle of 1s for each arrangement.

For every permutation:

1. Rearrange the matrix columns.
2. Compute the largest all-ones submatrix.
3. Track the maximum area.

This works because trying all permutations guarantees we eventually examine the optimal arrangement.

However, the number of permutations is n!, which is astronomically large even for moderate values of n. Even if rectangle checking were efficient, the permutation count makes this completely infeasible.

Another brute force variant might enumerate all possible submatrices and check whether some column rearrangement can make them all ones. This is also prohibitively expensive.

We need a better insight.

Key Insight

The crucial observation is that column order only matters relative to the heights of consecutive 1s ending at the current row.

Suppose we preprocess the matrix so that each cell stores the height of consecutive 1s ending at that position vertically.

For example:

Original:
1 0 1
1 1 1
1 0 1

Heights:
1 0 1
2 1 2
3 0 3

Now consider one row of heights:

2 1 2

If we sort these heights in descending order:

2 2 1

then:

• Using width 1, height is 2, area = 2
• Using width 2, height is 2, area = 4
• Using width 3, height is 1, area = 3

The best area is 4.

Why does sorting work?

Because after rearranging columns, we can place taller columns next to each other. If the sorted heights are:

h1 >= h2 >= h3 ...

then for width k, the limiting height is hk, giving area:

hk * k

So for every row:

1. Compute consecutive heights.
2. Sort the row descending.
3. Compute the best rectangle using each position as the minimum height.

This reduces the problem to efficient histogram processing.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! * m * n)	O(m * n)	Tries all column permutations
Optimal	O(m * n log n)	O(n) or O(m * n)	Uses histogram heights and sorting

Algorithm Walkthrough

1. Create a height representation of the matrix.

For every cell, compute the number of consecutive 1s ending at that row vertically.

If matrix[row][col] == 1:

• If it is the first row, height is 1
• Otherwise:

height[row][col] = height[row - 1][col] + 1

If the cell contains 0, the height becomes 0. 2. Process each row independently.

Each row now represents histogram heights ending at that row. 3. Sort the row in descending order.

Since we can rearrange columns arbitrarily, the best arrangement places taller columns first. 4. Compute rectangle areas.

For every position i in the sorted row:

• Width = i + 1
• Height = sorted_heights[i]

Area becomes:

area = height * width

5. Track the global maximum area.

Update the answer whenever a larger rectangle is found. 6. Return the maximum area after processing all rows.

Why it works

For any rectangle ending at a particular row, the rectangle height is constrained by the shortest column included in that rectangle.

Sorting heights descending ensures that when we take the first k columns, the smallest height among them is maximized. Therefore, the best rectangle of width k is always obtained by using the k tallest columns.

By checking every possible width after sorting each row, we examine every optimal candidate rectangle.

Python Solution

from typing import List

class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        rows = len(matrix)
        cols = len(matrix[0])

        # Build height histogram in-place
        for row in range(1, rows):
            for col in range(cols):
                if matrix[row][col] == 1:
                    matrix[row][col] += matrix[row - 1][col]

        max_area = 0

        for row in matrix:
            sorted_heights = sorted(row, reverse=True)

            for width, height in enumerate(sorted_heights, start=1):
                area = width * height
                max_area = max(max_area, area)

        return max_area

The implementation first converts the matrix into a vertical height histogram representation. Instead of allocating another matrix, the input matrix is updated in-place to save space.

For every cell containing 1, we accumulate the consecutive vertical count from the row above. Cells containing 0 naturally reset the height to zero.

After preprocessing, each row behaves like a histogram. Since columns may be rearranged freely, we sort each row in descending order. This simulates placing the tallest columns together.

The loop using enumerate(..., start=1) treats the current index as the rectangle width. The current height becomes the limiting height for that width. Multiplying them gives the candidate area.

The algorithm checks every possible rectangle ending at every row and keeps the largest area found.

Go Solution

package main

import "sort"

func largestSubmatrix(matrix [][]int) int {
	rows := len(matrix)
	cols := len(matrix[0])

	// Build height histogram in-place
	for row := 1; row < rows; row++ {
		for col := 0; col < cols; col++ {
			if matrix[row][col] == 1 {
				matrix[row][col] += matrix[row-1][col]
			}
		}
	}

	maxArea := 0

	for _, row := range matrix {
		heights := make([]int, cols)
		copy(heights, row)

		sort.Sort(sort.Reverse(sort.IntSlice(heights)))

		for width, height := range heights {
			area := (width + 1) * height

			if area > maxArea {
				maxArea = area
			}
		}
	}

	return maxArea
}

The Go implementation follows the same logic as the Python version.

One important difference is that Go sorting is performed in-place. Since we do not want to destroy the original row ordering while iterating, we first copy the row into a separate slice before sorting.

Go slices are reference-backed, so failing to copy would mutate the original matrix row directly.

Integer overflow is not a concern here because the maximum possible area is at most 10^5, which easily fits inside Go's int.

Worked Examples

Example 1

Input:

[
  [0,0,1],
  [1,1,1],
  [1,0,1]
]

Step 1: Build Heights

Row	Heights
0	[0,0,1]
1	[1,1,2]
2	[2,0,3]

Step 2: Process Each Row

Row 0

Original heights:

[0,0,1]

Sorted descending:

[1,0,0]

Width	Height	Area
1	1	1
2	0	0
3	0	0

Best so far: 1

Row 1

Original heights:

[1,1,2]

Sorted descending:

[2,1,1]

Width	Height	Area
1	2	2
2	1	2
3	1	3

Best so far: 3

Row 2

Original heights:

[2,0,3]

Sorted descending:

[3,2,0]

Width	Height	Area
1	3	3
2	2	4
3	0	0

Best overall: 4

Answer:

4

Example 2

Input:

[[1,0,1,0,1]]

Heights are already:

[1,0,1,0,1]

Sorted:

[1,1,1,0,0]

Width	Height	Area
1	1	1
2	1	2
3	1	3
4	0	0
5	0	0

Maximum area:

3

Example 3

Input:

[
  [1,1,0],
  [1,0,1]
]

Heights

Row	Heights
0	[1,1,0]
1	[2,0,1]

Process Rows

Row 0

Sorted:

[1,1,0]

Areas:

Width	Height	Area
1	1	1
2	1	2
3	0	0

Best: 2

Row 1

Sorted:

[2,1,0]

Areas:

Width	Height	Area
1	2	2
2	1	2
3	0	0

Final answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m * n log n)	Each row is sorted independently
Space	O(n)	Extra space used for sorting rows

The preprocessing step that builds histogram heights takes O(m * n) time.

For each of the m rows, we sort n heights. Sorting costs O(n log n) per row, giving a total complexity of:

O(m * n log n)

The Python implementation uses temporary sorted arrays of size n, while the Go implementation explicitly allocates a copy slice of size n. Therefore, auxiliary space is O(n).

Test Cases

from typing import List

class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        rows = len(matrix)
        cols = len(matrix[0])

        for row in range(1, rows):
            for col in range(cols):
                if matrix[row][col] == 1:
                    matrix[row][col] += matrix[row - 1][col]

        max_area = 0

        for row in matrix:
            sorted_heights = sorted(row, reverse=True)

            for width, height in enumerate(sorted_heights, start=1):
                max_area = max(max_area, width * height)

        return max_area

solver = Solution()

assert solver.largestSubmatrix([[0,0,1],[1,1,1],[1,0,1]]) == 4
# Provided example with rearrangement producing area 4

assert solver.largestSubmatrix([[1,0,1,0,1]]) == 3
# Single row matrix

assert solver.largestSubmatrix([[1,1,0],[1,0,1]]) == 2
# Cannot create larger rectangle

assert solver.largestSubmatrix([[1]]) == 1
# Smallest all-ones matrix

assert solver.largestSubmatrix([[0]]) == 0
# Smallest all-zeros matrix

assert solver.largestSubmatrix([[1,1],[1,1]]) == 4
# Entire matrix is valid

assert solver.largestSubmatrix([[0,0],[0,0]]) == 0
# No rectangle exists

assert solver.largestSubmatrix([[1],[1],[1]]) == 3
# Single column vertical accumulation

assert solver.largestSubmatrix([[1,0],[1,1],[1,1]]) == 4
# Tall rectangle after sorting

assert solver.largestSubmatrix([[1,0,1],[1,1,1],[0,1,1]]) == 4
# Multiple possible optimal rectangles

Test Case Summary

Test	Why
[[0,0,1],[1,1,1],[1,0,1]]	Standard mixed matrix example
[[1,0,1,0,1]]	Single row behavior
[[1,1,0],[1,0,1]]	Rearrangement limitations
[[1]]	Minimum valid matrix
[[0]]	Minimum zero matrix
[[1,1],[1,1]]	Entire matrix forms rectangle
[[0,0],[0,0]]	No valid rectangle
[[1],[1],[1]]	Single column accumulation
[[1,0],[1,1],[1,1]]	Tall rectangle creation
[[1,0,1],[1,1,1],[0,1,1]]	Multiple competing rectangles

Edge Cases

One important edge case is a matrix containing only zeros. In this situation, every histogram height remains zero throughout preprocessing. After sorting, every candidate rectangle area is also zero. A buggy implementation might accidentally assume at least one valid rectangle exists, but this solution naturally returns zero because all computed areas remain zero.

Another important edge case is a single row matrix. Since there is no vertical accumulation, the algorithm effectively becomes a problem of grouping all 1s together through column rearrangement. Sorting the row correctly places all 1s first, allowing the algorithm to compute the maximum contiguous width directly.

A third critical edge case is a single column matrix. Since column rearrangement has no effect when only one column exists, the algorithm must still correctly compute vertical consecutive heights. The histogram accumulation step handles this naturally by counting consecutive 1s downward.

A subtle edge case occurs when different columns have different heights. For example:

[3,1,2]

If the row is not sorted before area computation, we may incorrectly underestimate the best rectangle. Sorting ensures the tallest columns are grouped first, maximizing the minimum height for every width.

Another tricky case involves rows where zeros interrupt accumulation. Whenever a cell contains 0, its height must reset to zero rather than continuing accumulation from above. The implementation handles this correctly because heights are only incremented when the current cell equals 1.