Problem Description

You have a binary matrix (containing only 0s and 1s) with dimensions m x n. You can rearrange the columns of this matrix in any order you want.

Your goal is to find the largest possible rectangular area that contains only 1s after optimally rearranging the columns.

For example, if you have a matrix where some columns have consecutive 1s, you can rearrange these columns to be adjacent to each other, potentially creating a larger rectangle of 1s than what existed in the original arrangement.

The problem asks you to:

1. Consider all possible ways to rearrange the columns
2. Find the arrangement that gives you the largest rectangular submatrix containing only 1s
3. Return the area of that largest submatrix

Note that you can only rearrange entire columns - you cannot rearrange individual elements or rows. Each column moves as a complete unit when rearranged.

Intuition

The key insight is that when we can rearrange columns freely, we want to group columns with consecutive 1s together to form larger rectangles.

Let's think about what happens when we look at each row as a potential bottom edge of our rectangle. For any row, if we know the height of consecutive 1s extending upward from each position, we can determine the best rectangle with that row as the base.

First observation: If we transform each cell matrix[i][j] that contains a 1 to represent the number of consecutive 1s above it (including itself), we get valuable height information. For example, if matrix[i][j] = 3, it means there are 3 consecutive 1s from row i going upward in column j.

Second observation: Once we have these heights for a particular row, we can rearrange the columns optimally. How? By sorting the heights in descending order!

Why does sorting work? Consider a row with heights [3, 1, 2, 4]. After sorting in descending order: [4, 3, 2, 1]. Now:

• Using just the first column (height 4), we get area = 4 × 1 = 4
• Using the first two columns (minimum height 3), we get area = 3 × 2 = 6
• Using the first three columns (minimum height 2), we get area = 2 × 3 = 6
• Using all four columns (minimum height 1), we get area = 1 × 4 = 4

By sorting, we ensure that when we consider k columns, we're taking the k tallest columns available, maximizing our potential area. The area with k columns is min_height × k, and sorting guarantees we're always working with the best possible minimum height for any given width.

This approach cleverly sidesteps the need to explicitly try all column permutations by recognizing that for each row, the optimal arrangement is simply to sort by height.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation consists of two main phases: preprocessing and calculating the maximum area.

Phase 1: Preprocessing - Building Height Matrix

We iterate through the matrix starting from the second row (index 1) and update each cell that contains a 1:

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

This transforms each cell matrix[i][j] from a binary value to the count of consecutive 1s extending upward from that position. If matrix[i][j] is 0, it remains 0. If it's 1, it becomes matrix[i-1][j] + 1, accumulating the height of the column of 1s.

For example, a column [1, 1, 1, 0, 1] becomes [1, 2, 3, 0, 1] after preprocessing.

Phase 2: Finding Maximum Area

For each row in the preprocessed matrix:

for row in matrix:
    row.sort(reverse=True)
    for j, v in enumerate(row, 1):
        ans = max(ans, j * v)

1. Sort each row in descending order: This rearranges the columns optimally for that row. The tallest columns come first.

2. Calculate potential areas: For each position j (1-indexed) with height v:

   • The area is j * v because:
     • We're considering the first j columns (after sorting)
     • The minimum height among these j columns is v (since they're sorted)
     • Rectangle area = width × height = j × v

3. Track the maximum: We update ans with the maximum area found across all rows and all possible rectangle widths.

The algorithm efficiently explores all possible rectangles by:

• Using each row as a potential bottom edge
• Leveraging sorting to automatically find the optimal column arrangement for each row
• Computing areas for all possible widths in the sorted arrangement

Time complexity: O(m × n × log n) where m is the number of rows and n is the number of columns (due to sorting each row). Space complexity: O(1) extra space as we modify the matrix in place.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this 3×4 binary matrix:

1 0 1 0
1 1 1 1
1 1 0 1

Phase 1: Building the Height Matrix

We transform each cell to represent the count of consecutive 1s extending upward from that position.

Starting with row 1 (index 1):

• Position [1][0]: has a 1, and above it is also 1, so it becomes 1 + 1 = 2
• Position [1][1]: has a 1, but above it is 0, so it stays 1
• Position [1][2]: has a 1, and above it is also 1, so it becomes 1 + 1 = 2
• Position [1][3]: has a 1, but above it is 0, so it stays 1

After processing row 1:

1 0 1 0
2 1 2 1
1 1 0 1

Processing row 2 (index 2):

• Position [2][0]: has a 1, and above it is 2, so it becomes 2 + 1 = 3
• Position [2][1]: has a 1, and above it is 1, so it becomes 1 + 1 = 2
• Position [2][2]: has a 0, so it stays 0
• Position [2][3]: has a 1, and above it is 1, so it becomes 1 + 1 = 2

Final height matrix:

1 0 1 0
2 1 2 1
3 2 0 2

Phase 2: Finding Maximum Area

Now we process each row, sort it in descending order, and calculate possible areas.

Row 0: [1, 0, 1, 0]

• After sorting: [1, 1, 0, 0]
• Position 1: width=1, height=1, area = 1×1 = 1
• Position 2: width=2, height=1, area = 2×1 = 2
• Position 3: width=3, height=0, area = 3×0 = 0
• Position 4: width=4, height=0, area = 4×0 = 0
• Maximum for this row: 2

Row 1: [2, 1, 2, 1]

• After sorting: [2, 2, 1, 1]
• Position 1: width=1, height=2, area = 1×2 = 2
• Position 2: width=2, height=2, area = 2×2 = 4
• Position 3: width=3, height=1, area = 3×1 = 3
• Position 4: width=4, height=1, area = 4×1 = 4
• Maximum for this row: 4

Row 2: [3, 2, 0, 2]

• After sorting: [3, 2, 2, 0]
• Position 1: width=1, height=3, area = 1×3 = 3
• Position 2: width=2, height=2, area = 2×2 = 4
• Position 3: width=3, height=2, area = 3×2 = 6
• Position 4: width=4, height=0, area = 4×0 = 0
• Maximum for this row: 6

Final Answer: 6

The largest rectangular area of 1s is 6, achieved by using row 2 as the bottom edge and rearranging columns to place the three tallest columns (heights 3, 2, 2) adjacent to each other, forming a 3×2 rectangle.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n × log n) where m is the number of rows and n is the number of columns in the matrix.

• The first nested loop runs through all elements of the matrix once to calculate consecutive heights: O(m × n)
• The second part iterates through each row (m rows) and sorts each row which takes O(n log n) time
• After sorting, we iterate through each sorted row once: O(n) per row
• Total for the second part: O(m × (n log n + n)) = O(m × n × log n)
• Overall time complexity: O(m × n) + O(m × n × log n) = O(m × n × log n) (dominated by the sorting operation)

Space Complexity: O(1) if we don't count the modification of the input matrix, or O(m × n) if we consider the input matrix modification as extra space.

• The algorithm modifies the input matrix in-place to store the consecutive heights
• The sorting operation uses O(log n) space for the sorting algorithm's recursion stack (Python's Timsort)
• No additional data structures are created apart from a few variables (ans, i, j, v)
• If modifying the input is not allowed and we need to preserve the original matrix, we would need O(m × n) extra space to create a copy

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Sorting Logic

The Problem: A common mistake is thinking that sorting the heights in descending order arbitrarily rearranges values. In reality, sorting represents the optimal rearrangement of columns for maximizing rectangular areas at each row level.

Why This Happens: When we sort row = [3, 0, 2, 1] to get [3, 2, 1, 0], we're not just sorting numbers - we're rearranging entire columns based on their heights at this row. The confusion arises because after preprocessing, each value represents a column's height, not just a single cell.

Solution: Remember that each value after preprocessing represents the height of consecutive 1s in that column up to the current row. Sorting these heights allows us to group the tallest columns together, which maximizes potential rectangle areas.

Pitfall 2: Incorrect Area Calculation After Sorting

The Problem: Developers sometimes calculate the area as height * original_width or use incorrect indexing like row[j] * (j+1) when j is 0-indexed.

Example of Wrong Implementation:

for j in range(len(row)):
    area = row[j] * (j + 1)  # Wrong when j is 0-indexed

Why This Fails: After sorting in descending order, the width of a valid rectangle at position j (0-indexed) is actually j+1 because we can use columns from index 0 to j inclusive. The height is limited by the minimum height in this range, which is row[j] due to descending order.

Solution: Use 1-indexed enumeration for clarity:

for width, height in enumerate(row, start=1):
    area = width * height

Pitfall 3: Not Handling Edge Cases

The Problem: The algorithm might fail or give incorrect results for:

• Empty matrices
• Single row or single column matrices
• Matrices with all 0s

Why This Happens: The preprocessing loop starts from index 1, which assumes at least 2 rows exist. For single-row matrices, the preprocessing loop never executes, but this is actually correct behavior since no accumulation is needed.

Solution: The current implementation actually handles these cases correctly:

• Single row: Preprocessing is skipped, sorting still works
• All 0s: Heights remain 0, maximum area is 0
• Empty matrix: Returns 0 (though checking for empty input is good practice)

For extra safety, you could add:

if not matrix or not matrix[0]:
    return 0

Pitfall 4: Modifying the Input Matrix

The Problem: The solution modifies the input matrix in-place during preprocessing. This could be unexpected behavior if the caller needs the original matrix preserved.

Why This Matters: In interview settings or production code, modifying input parameters without documentation can lead to bugs in calling code that expects the matrix to remain unchanged.

Solution: Either:

1. Document that the function modifies the input
2. Create a copy of the matrix:

matrix = [row[:] for row in matrix]  # Create a deep copy

3. Use a separate height matrix:

heights = [[0] * len(matrix[0]) for _ in range(len(matrix))]