LeetCode 1727: Largest Submatrix With Rearrangements (Java Explanation)

Matrix problems often look simple but hide powerful tricks. In LeetCode 1727 – Largest Submatrix With Rearrangements, the key insight is realizing that we can rearrange columns to maximize the area of a rectangle made of 1s.

In this tutorial we will cover:

• Problem explanation in simple terms
• Walkthrough of the example
• The key intuition behind the solution
• Step-by-step Java implementation
• Time complexity analysis

Problem Statement

You are given a binary matrix containing only 0s and 1s. You can rearrange the columns of the matrix in any order for each row.

Your goal is to find the largest rectangular submatrix containing only 1s.

Example

We want to rearrange columns to form the largest possible rectangle of 1s.

Key Idea (Important Trick)

Instead of searching for rectangles directly, we convert each row into heights of consecutive 1s.

This converts the matrix into histogram-like values.

Step 1: Build Heights

Each value represents the height of consecutive 1s above that cell.

Step 2: Rearrange Columns

Because we are allowed to rearrange columns, the order of columns doesn't matter.

So we simply sort each row in descending order.

Step 3: Calculate Rectangle Area

For each position, compute:

Area = height × width

3 × 1 = 3
2 × 2 = 4
0 × 3 = 0

Maximum area = 4

Java Implementation

class Solution {

    public int largestSubmatrix(int[][] matrix) {

        int m = matrix.length;
        int n = matrix[0].length;

        int[][] height = new int[m][n];

        for(int j=0;j<n;j++)
            height[0][j] = matrix[0][j];

        for(int i=1;i<m;i++){

            for(int j=0;j<n;j++){

                if(matrix[i][j] == 1)
                    height[i][j] = height[i-1][j] + 1;
                else
                    height[i][j] = 0;
            }
        }

        int maxArea = 0;

        for(int i=0;i<m;i++){

            int[] row = height[i].clone();

            java.util.Arrays.sort(row);

            for(int j=n-1;j>=0;j--){

                int width = n - j;

                int area = row[j] * width;

                maxArea = Math.max(maxArea, area);
            }
        }

        return maxArea;
    }
}

Time Complexity

Building heights:

O(m × n)

Sorting each row:

O(m × n log n)

Total complexity:

O(m × n log n)

Why This Solution Works

Alternative Approaches

1. Brute Force

Check every possible rectangle.

O(m² × n²)

Too slow for large matrices.

2. Counting Sort Optimization

Since heights are limited by number of rows, we can replace sorting with counting sort.

This slightly improves performance.

Video Explanation

Watch the full visual explanation here:

Conclusion

The key insight for solving this problem is converting the matrix into histogram heights and then sorting each row to maximize rectangle width.

Once you see this trick, the problem becomes much easier to implement.