Problem Statement
You are given an n × m grid and k blocked cells.
Each blocked cell blocks:
Its entire row
Its entire column
Your task is to find the largest continuous rectangular area that remains completely unblocked.
Note: No two blocked cells lie in the same row or the same column.
Observation
A blocked cell does not just block one position.
For example, if there is a blocked cell at (3,4):
Rows
1 2 3 4 5
Columns
1 2 3 4 5
↓
1 . . . X .
2 . . . X .
3 X X X X X
4 . . . X .
5 . . . X .
Entire row 3 and entire column 4 become unusable.
So, after blocking:
Therefore, we only need to find the largest gap between blocked rows and blocked columns.
Key Insight
Instead of looking at every cell, we only care about:
Blocked row numbers
Blocked column numbers
Because they divide the grid into several rectangles.
The answer is:
Largest free row segment
×
Largest free column segment
Example 1
Suppose:
n = 8
m = 9
Blocked rows:
2
6
Blocked columns:
3
8
Rows
0 2 6 9
Here:
Gap Calculation
Between 0 and 2:
Rows:
1
Length = 1
Between 2 and 6:
Rows:
3 4 5
Length = 3
Between 6 and 9:
Rows:
7 8
Length = 2
Maximum free rows:
= 3
Columns
0 3 8 10
Gap Calculation
0 → 3
Columns
1 2
Length = 2
3 → 8
Columns
4 5 6 7
Length = 4
8 → 10
Column
9
Length = 1
Maximum free columns:
= 4
Therefore:
Largest rectangle
= 3 × 4
= 12
Why Add Boundaries?
Suppose:
Rows
1 2 3 4 5
Blocked row = 3
Without boundaries, only one blocked row exists.
How do we know:
Rows 1-2
Rows 4-5
So we imagine:
0 3 6
Now gaps become:
3 - 0 - 1 = 2
Rows
1 2
6 - 3 - 1 = 2
Rows
4 5
Hence, always add:
0
n + 1
Similarly for columns:
0
m + 1
Why Subtract 1?
Suppose blocked rows are:
2
6
2 ..... 6
Rows between them are:
3
4
5
Count:
6 - 2 - 1
= 3
General formula:
gap = current - previous - 1
Algorithm
Step 1
Store blocked rows.
rows = {blocked rows}
Store blocked columns.
cols = {blocked columns}
Step 2
Add boundaries.
rows.add(0);
rows.add(n + 1);
cols.add(0);
cols.add(m + 1);
Step 3
Sort both arrays.
Rows:
0 2 6 9
Columns:
0 3 8 10
Step 4
Find maximum row gap.
maxRow = 0;
for every adjacent pair
gap = rows[i] - rows[i - 1] - 1;
maxRow = max(maxRow, gap);
Step 5
Find maximum column gap.
maxCol = 0;
gap = cols[i] - cols[i - 1] - 1;
Step 6
Answer:
maxRow × maxCol
Dry Run
Input
n = 5
m = 5
Blocked cells
(2,3)
(5,1)
Blocked Rows
2
5
Add boundaries:
0 2 5 6
Find gaps:
2 - 0 - 1 = 1
Rows
1
5 - 2 - 1 = 2
Rows
3 4
6 - 5 - 1 = 0
Maximum:
2
Blocked Columns
3
1
After sorting:
0 1 3 6
Gaps:
1 - 0 - 1 = 0
3 - 1 - 1 = 1
6 - 3 - 1 = 2
Maximum:
2
Area
2 × 2
= 4
Correctness Proof
Let:
Any valid rectangle cannot cross a blocked row or a blocked column. Therefore:
A rectangle using the largest row segment and the largest column segment is entirely unblocked because blocked rows and blocked columns partition the grid independently.
Hence, the largest possible rectangle has area:
R × C
Thus, the algorithm always returns the optimal answer.
Complexity Analysis
Let k be the number of blocked cells.
Sorting Rows
O(k log k)
Sorting Columns
O(k log k)
Gap Calculation
O(k)
Overall Time Complexity
O(k log k)
Auxiliary Space
O(k)
Java Implementation
import java.util.*;
class Solution {
public int largestArea(int n, int m, int k, int[][] arr) {
ArrayList<Integer> rows = new ArrayList<>();
ArrayList<Integer> cols = new ArrayList<>();
rows.add(0);
cols.add(0);
for (int i = 0; i < k; i++) {
rows.add(arr[i][0]);
cols.add(arr[i][1]);
}
rows.add(n + 1);
cols.add(m + 1);
Collections.sort(rows);
Collections.sort(cols);
int maxRow = 0;
int maxCol = 0;
for (int i = 1; i < rows.size(); i++) {
maxRow = Math.max(maxRow, rows.get(i) - rows.get(i - 1) - 1);
}
for (int i = 1; i < cols.size(); i++) {
maxCol = Math.max(maxCol, cols.get(i) - cols.get(i - 1) - 1);
}
return maxRow * maxCol;
}
}
Takeaway
The key insight is to avoid examining every cell of the grid. Since a blocked cell eliminates its entire row and column, the grid is effectively partitioned by the blocked rows and columns. By finding the largest gap between consecutive blocked rows and the largest gap between consecutive blocked columns, we can directly compute the maximum unblocked rectangle as:
Largest Area = Max Free Row Gap × Max Free Column Gap
This transforms what could be an O(n × m) grid problem into an efficient O(k log k) solution using sorting and greedy gap computation.
Summary
Instead of evaluating every cell in the grid, this solution focuses only on the blocked rows and columns. By adding boundary markers, sorting the blocked positions, and finding the maximum gaps between consecutive blocked rows and columns, we can determine the largest available rectangular region. The final area is simply the product of the largest free row segment and the largest free column segment, resulting in an optimal O(k log k) solution.