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:
6
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:
6
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:
3
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:
6
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:
6
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.”