Largest Rectangle with Column Swaps

1. Problem Statement

We are given a binary matrix containing only 0 and 1.

We are allowed to swap any two columns any number of times.

Our goal is to find the maximum possible area of a rectangle containing only 1s after performing column swaps.

For example:

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

The answer is:

The important observation is that we are allowed to rearrange columns, so we don't need to preserve their original order.

2. Main Idea

We process the matrix row by row.

For every column, we maintain the number of continuous 1s ending at the current row.

For example:

0 1 1
1 1 1
1 1 0

After processing row 0:

0 1 1

After processing row 1:

1 2 2

After processing row 2:

2 3 0

Here:

height[j]

represents the number of consecutive 1s in column j ending at the current row.

3. Why Can We Sort the Heights?

This is the most important part of the problem.

Suppose at some row we have:

height = [2, 5, 3, 1, 4]

Because columns can be swapped, we can rearrange them as:

[5, 4, 3, 2, 1]

Now the largest heights can be placed next to each other.

For example:

5 4 3 2 1

If we choose the first 3 columns, the minimum height is 3.

Therefore, we can create:

Height = 3
Width  = 3

Area = 3 × 3 = 9

So after sorting, we simply check every possible width.

4. Java Code

import java.util.*;

class Solution {
    public int maxArea(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;

        int[] height = new int[m];
        int maxArea = 0;

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

            // Calculate consecutive 1s for each column
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 1) {
                    height[j]++;
                } else {
                    height[j] = 0;
                }
            }

            // Copy heights
            int[] sorted = height.clone();

            // Sort heights
            Arrays.sort(sorted);

            // Try every possible width
            for (int j = m - 1; j >= 0; j--) {
                int width = m - j;
                int area = sorted[j] * width;

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

        return maxArea;
    }
}

5. Line-by-Line Explanation

Step 1: Get matrix dimensions

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

n = number of rows.

m = number of columns.

For:

3 × 5

we have:

n = 3
m = 5

Step 2: Create the height array

int[] height = new int[m];

This stores the number of consecutive 1s for every column.

Initially:

height = [0, 0, 0, 0, 0]

Step 3: Process every row

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

We process one row at a time.

Step 4: Update the heights

for (int j = 0; j < m; j++) {
    if (mat[i][j] == 1) {
        height[j]++;
    } else {
        height[j] = 0;
    }
}

If the current cell is 1:

height[j]++;

We increase the consecutive height.

If the current cell is 0:

height[j] = 0;

The consecutive sequence is broken.

Example

Consider:

1 1 0
1 1 1
1 0 1

After first row:

1 1 0

After second row:

2 2 1

After third row:

3 0 2

So the height array represents vertical rectangles ending at the current row.

6. Copy the Heights

int[] sorted = height.clone();

We create a copy because we don't want to modify the original height array.

For example:

height = [3, 1, 4, 2]

After cloning:

sorted = [3, 1, 4, 2]

7. Sort the Heights

Arrays.sort(sorted);

After sorting:

[1, 2, 3, 4]

We can conceptually arrange the columns in this order because column swapping is allowed.

8. Calculate the Area

for (int j = m - 1; j >= 0; j--) {
    int width = m - j;
    int area = sorted[j] * width;

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

Suppose:

sorted = [1, 2, 3, 4]

We process from the largest height.

First

height = 4
width = 1

area = 4 × 1 = 4

Second

height = 3
width = 2

area = 3 × 2 = 6

Third

height = 2
width = 3

area = 2 × 3 = 6

Fourth

height = 1
width = 4

area = 1 × 4 = 4

Maximum:

9. Why Does `sorted[j] × width` Work?

Suppose:

sorted = [1, 3, 3, 4, 4]

For the last two columns:

4 4

we can create:

Height = 4
Width = 2
Area = 8

For the last three columns:

3 4 4

the minimum height is 3.

Therefore:

Height = 3
Width = 3
Area = 9

For the last four:

3 3 4 4

the minimum height is 3.

Therefore:

Height = 3
Width = 4
Area = 12

So:

Maximum Area = 12

10. Complete Dry Run

Consider:

1 1 1
1 1 1
1 1 0

Row 0

height = [1, 1, 1]

Sorted:

[1, 1, 1]

Areas:

1 × 1 = 1
1 × 2 = 2
1 × 3 = 3

Maximum:

Row 1

All values are 1:

height = [2, 2, 2]

Sorted:

[2, 2, 2]

Areas:

2 × 1 = 2
2 × 2 = 4
2 × 3 = 6

Maximum:

Row 2

The last value is 0:

height = [3, 3, 0]

Sorted:

[0, 3, 3]

Areas:

3 × 1 = 3
3 × 2 = 6
0 × 3 = 0

Final answer:

11. Important Observation

This problem looks like the Largest Rectangle in Histogram problem, but there is an important difference.

In a normal histogram:

[2, 5, 3, 1, 4]

we cannot rearrange the bars.

Here, we can swap columns, so we can arrange them:

[5, 4, 3, 2, 1]

Therefore, after calculating the heights, sorting is enough.

12. Complexity

The above implementation uses:

Arrays.sort(sorted);

Sorting m elements takes:

O(m log m)

We do this for n rows.

Therefore:

Time Complexity = O(n × m log m)

Space:

height = O(m)
sorted = O(m)

So auxiliary space is:

O(m)

13. Expected O(n × (n + m)) Approach

The problem's expected complexity is:

O(n × (n + m))

Why can we do better than sorting?

Because every height value is between:

0 and n

There are only n + 1 possible height values.

Therefore, instead of using:

Arrays.sort()

we can use counting sort.

That gives:

O(m + n)

for each row.

For all rows:

O(n × (m + n))

which matches the expected complexity.

14. Expected-Complexity Java Solution

class Solution {
    public int maxArea(int[][] mat) {

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

        int[] height = new int[m];
        int maxArea = 0;

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

            // Build histogram heights
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 1) {
                    height[j]++;
                } else {
                    height[j] = 0;
                }
            }

            // Counting sort
            int[] count = new int[n + 1];

            for (int j = 0; j < m; j++) {
                count[height[j]]++;
            }

            // Process heights from largest to smallest
            int width = 0;

            for (int h = n; h >= 0; h--) {

                if (count[h] > 0) {

                    width += count[h];

                    int area = h * width;

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

        return maxArea;
    }
}

Complexity of this version

For every row:

Build heights     → O(m)
Counting          → O(m)
Process counts    → O(n)

Therefore:

Total = O(n × (m + n))

which is the expected complexity.

Interview explanation in one sentence

“For each row, I maintain the consecutive vertical 1s for every column. Since arbitrary column swaps are allowed, I can rearrange these heights in descending order and evaluate every possible width. Using counting sort because heights are bounded by n, the solution runs in O(n × (n + m)) time.”

1. Problem Statement

2. Main Idea

3. Why Can We Sort the Heights?

4. Java Code

5. Line-by-Line Explanation

Step 1: Get matrix dimensions

Step 2: Create the height array

Step 3: Process every row

Step 4: Update the heights

Example

6. Copy the Heights

7. Sort the Heights

8. Calculate the Area

First

Second

Third

Fourth

9. Why Does sorted[j] × width Work?

10. Complete Dry Run

Row 0

Row 1

Row 2

11. Important Observation

12. Complexity

13. Expected O(n × (n + m)) Approach

14. Expected-Complexity Java Solution

Complexity of this version

Interview explanation in one sentence

9. Why Does `sorted[j] × width` Work?