Topics › Stacks and Queues › Monotonic Stack/Queue Problems [VVV. Imp]

Maximum Rectangles

Hard TUF ID 962 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an n × m binary matrix whose cells are the characters '0' and '1'. Return the area of the largest axis-aligned rectangle that contains only '1' cells. This is the problem known on LeetCode as Maximal Rectangle.

Constraints: 1 ≤ n, m ≤ 200 on LeetCode. The Java file also accepts an empty matrix and returns 0.

Example 1

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
answer = 6     // rows 1-2, columns 2-4

Example 2

0 1 1 0
1 1 1 1
1 1 1 1
0 1 1 0
answer = 8     // rows 1-2 across all 4 columns, or columns 1-2 down all 4 rows

A single '0' gives 0; a single '1' gives 1.

Approach 1: Brute force with a 2D prefix sum

Intuition. A rectangle is fixed by its top-left corner (r1, c1) and bottom-right corner (r2, c2). There are O(n^2 m^2) of them. A rectangle is valid when the number of '1' cells inside equals its area. Counting the 1s cell by cell would add another O(nm) factor, so precompute a 2D prefix sum: pre[i][j] is the number of 1s in rows < i and columns < j. Then the count for any rectangle comes from four lookups by inclusion and exclusion.

Algorithm.

1. Build pre with pre[i+1][j+1] = pre[i][j+1] + pre[i+1][j] - pre[i][j] + cell(i, j).
2. For every pair of corners, compute ones = pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1].
3. If ones equals the area, update the answer.

static int bruteForce(char[][] matrix) {
    int n = matrix.length;
    if (n == 0) return 0;
    int m = matrix[0].length;
    int[][] pre = new int[n + 1][m + 1];           // pre[i][j] = number of 1s in rows < i and columns < j
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            pre[i + 1][j + 1] = pre[i][j + 1] + pre[i + 1][j] - pre[i][j] + (matrix[i][j] == '1' ? 1 : 0);
    int best = 0;
    for (int r1 = 0; r1 < n; r1++)
        for (int c1 = 0; c1 < m; c1++)
            for (int r2 = r1; r2 < n; r2++)
                for (int c2 = c1; c2 < m; c2++) {
                    int area = (r2 - r1 + 1) * (c2 - c1 + 1);
                    int ones = pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1] - pre[r2 + 1][c1] + pre[r1][c1];
                    if (ones == area) best = Math.max(best, area);
                }
    return best;
}

Complexity. Time O(n^2 m^2): for a 200 × 200 matrix that is about 1.6 × 10^9 rectangles, too slow. Space O(nm) for the prefix sums.

Approach 2: Better, fix the bottom-right corner

Intuition. Let width[i][j] be the number of consecutive 1s that end at cell (i, j) going left in row i. Now fix a cell (i, j) as the bottom-right corner and grow the rectangle upward one row at a time. A rectangle covering rows k..i and ending at column j can be at most min(width[k..i][j]) wide, because every row in it needs that many 1s ending at column j. So walking k upward from i while tracking the running minimum width gives the best rectangle for every height in one sweep.

Algorithm.

1. For each cell (i, j) that is '1': width[i][j] = width[i][j-1] + 1 (or 1 at the first column).
2. Walk k from i upward, keep minWidth = min(minWidth, width[k][j]), and update the answer with minWidth × (i - k + 1).
3. Stop as soon as minWidth becomes 0: a row with no 1 at column j blocks every taller rectangle.

static int better(char[][] matrix) {
    int n = matrix.length;
    if (n == 0) return 0;
    int m = matrix[0].length;
    int[][] width = new int[n][m];                 // number of consecutive 1s ending at (i, j), going left
    int best = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == '0') continue;
            width[i][j] = (j == 0 ? 0 : width[i][j - 1]) + 1;
            int minWidth = width[i][j];
            for (int k = i; k >= 0 && minWidth > 0; k--) {
                minWidth = Math.min(minWidth, width[k][j]);
                best = Math.max(best, minWidth * (i - k + 1));
            }
        }
    }
    return best;
}

Complexity. Time O(n^2 m): each of the nm cells walks up at most n rows. Space O(nm) for width (one row of widths per row of the matrix).

Approach 3: Optimal, one histogram per row

Intuition. Turn the walk around: instead of looking left along a row, look up a column. For a fixed row i, let heights[j] be the number of consecutive 1s ending at row i in column j. Row i now looks like the floor of a histogram, with bar j of height heights[j].

Take any all-1 rectangle and look at its bottom row i. Every column it covers has at least as many consecutive 1s above row i (inclusive) as the rectangle is tall, so the rectangle fits under the histogram of row i. Conversely, every rectangle under that histogram is made of 1s. So:

answer = max over rows i of (largest rectangle in the histogram of row i)

The heights for row i come from row i - 1 in O(m): a '1' extends the bar by one, a '0' resets it to zero. The largest rectangle in a histogram takes O(m) with a monotonic stack (see the linked article for a full derivation). In short: keep an increasing stack of indices; when a bar not taller than the top arrives, the top has found its right boundary, its left boundary is the element below it, so pop and measure it. A final height-0 sentinel flushes the stack.

Algorithm.

1. Start with heights all zero.
2. For each row: update heights[j] to heights[j] + 1 for a '1' and 0 for a '0'.
3. Run largestRectangle(heights) and keep the maximum.

static int optimal(char[][] matrix) {
    if (matrix.length == 0) return 0;
    int m = matrix[0].length, best = 0;
    int[] heights = new int[m];
    for (char[] row : matrix) {
        for (int j = 0; j < m; j++) heights[j] = row[j] == '1' ? heights[j] + 1 : 0;
        best = Math.max(best, largestRectangle(heights));
    }
    return best;
}

static int largestRectangle(int[] heights) {
    int n = heights.length, best = 0;
    Deque<Integer> st = new ArrayDeque<>();
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];
        while (!st.isEmpty() && heights[st.peek()] >= h) {
            int height = heights[st.pop()];
            int leftBoundary = st.isEmpty() ? -1 : st.peek();
            best = Math.max(best, height * (i - leftBoundary - 1));
        }
        st.push(i);
    }
    return best;
}

Dry run on Example 1:

The answer is 6, found with row 2 as the base. Notice row 3: column 0 has a bar of height 4, which is the 4 × 1 vertical strip of ones, a different shape that the per-row view also catches.

Complexity. Time O(nm): each row costs O(m) to update the heights and O(m) for the stack pass. Space O(m) for heights and the stack.

Edge cases and pitfalls

• Characters, not integers. The cells are '0' and '1' (char codes 48 and 49). Comparing with 1 instead of '1' silently treats every cell as zero.
• Resetting heights. A '0' must reset the column to 0, not merely skip it; otherwise ones separated by a zero would be glued into one bar. The single-column test 1,1,0,1,1,1,1 expects 4, not 6.
• Ties between shapes. In Example 2 a wide and a tall rectangle both have area 8. Only the area is returned, so either is fine.
• Whole matrix. When every cell is '1', the last row’s histogram is flat and gives n × m.
• Empty matrix. Guard matrix.length == 0 before reading matrix[0].length.
• Orientation. Building histograms from rows (heights go down the columns) costs O(m) space. If m is much larger than n, building them along columns instead saves memory; the time is O(nm) either way.

Related problems

• Largest rectangle in a histogram is the subroutine called once per row.
• Maximum Rectangle Area with all 1’s - (DP-55) is the same problem listed in the DP section.
• Next Smaller Element is the stack primitive that finds each bar’s boundaries.
• Trapping Rainwater is another problem that reasons about bars and the walls around them.