Largest Unblocked Submatrix

Problem Overview

Blocked cells split the grid into horizontal and vertical strips.

Intuition

Blocked cells split the grid into horizontal and vertical strips. The largest all-1 submatrix must lie entirely between two consecutive blocked rows and two consecutive blocked columns. So collect blocked row/column indices, add grid boundaries, sort, and maximize (row gap) × (column gap).

Algorithm

1Gather all blocked row indices and column indices from the input.
2Append sentinel boundaries: rows 0 and n+1, columns 0 and m+1.
3Sort both lists.
4maxRowGap = maximum of (blockedRows[i] - blockedRows[i-1] - 1) over consecutive pairs.
5maxColGap = same for columns.
6Return maxRowGap * maxColGap.

Example Walkthrough

Input: n = 3, m = 3, blocked = [[1,1]]

1. Rows with boundaries: [0,1,4] → gaps 0 and 2 → maxRowGap = 2.
2. Columns with boundaries: [0,1,4] → maxColGap = 2.
3. Largest unblocked rectangle area = 2 × 2 = 4.

Output: 4

Common Pitfalls

• Include 0 and n+1 (not n) as row boundaries — gaps count interior rows only.
• Duplicate blocked indices are fine after sorting; gaps are between consecutive distinct boundaries.
• If every row or column is blocked, a gap can be 0 and the answer is 0.

Largest Unblocked Submatrix.java

Java

// Approach: Collect blocked row/col indices, add boundaries 0 and n+1 / m+1, sort, and take
// the maximum gap between consecutive blockers in each dimension. Answer = maxRowGap * maxColGap.
// Time: O(k log k) Space: O(k)  (k = number of blocked cells)

import java.util.*;

class Solution {

    public int largestArea(int n, int m, int[][] arr) {
        List<Integer> blockedRows = new ArrayList<>();
        List<Integer> blockedCols = new ArrayList<>();

        for (int[] cell : arr) {
            blockedRows.add(cell[0]);
            blockedCols.add(cell[1]);
        }

        // Add boundaries (0 and n+1 for rows, 0 and m+1 for cols)
        blockedRows.add(0);
        blockedRows.add(n + 1);
        blockedCols.add(0);
        blockedCols.add(m + 1);

        // Sort them
        Collections.sort(blockedRows);
        Collections.sort(blockedCols);

        // Find maximum gap in rows
        int maxRowGap = 0;
        for (int i = 1; i < blockedRows.size(); i++) {
            maxRowGap = Math.max(maxRowGap, blockedRows.get(i) - blockedRows.get(i - 1) - 1);
        }

        // Find maximum gap in columns
        int maxColGap = 0;
        for (int i = 1; i < blockedCols.size(); i++) {
            maxColGap = Math.max(maxColGap, blockedCols.get(i) - blockedCols.get(i - 1) - 1);
        }

        // Largest rectangle area
        return maxRowGap * maxColGap;
    }
}

Was this solution helpful?