☕ DSA Java Articles

Topics › Dynamic Programming › DP on Squares

Maximum Rectangle Area with all 1's - (DP-55)

Hard TUF ID 2860 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an n × m matrix containing only 0s and 1s. Find the largest axis-aligned rectangle that contains only 1s and return its area (the number of cells in it).

Constraints (LeetCode 85): 1 ≤ n, m ≤ 200. LeetCode passes the matrix as characters '0' and '1'; the Java file uses int values, and converting is a one-line change. The methods also return 0 for an empty matrix.

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 (0-indexed)

Example 2

1 1 0 1
1 1 0 1
0 1 1 1
answer = 4               // the 2 x 2 block at the top left; the longest line of ones only has 3 cells

Approach 1: Brute force with 2D prefix sums

Intuition. A rectangle is fixed by its top-left corner (r1, c1) and bottom-right corner (r2, c2), so there are O(n^2 m^2) of them. Checking each cell inside would add another O(nm) factor. A 2D prefix-sum table removes it: pre[i][j] counts the ones in rows < i and columns < j, and by inclusion-exclusion the number of ones in any rectangle is a combination of four table entries. The rectangle is all ones exactly when that count equals its area.

Algorithm.

  1. Build pre with pre[i+1][j+1] = matrix[i][j] + pre[i][j+1] + pre[i+1][j] - pre[i][j].
  2. For every pair of corners, compute the area and the number of ones inside.
  3. If they are equal, update the best area.
static int bruteForce(int[][] matrix) {
    int n = matrix.length, m = n == 0 ? 0 : matrix[0].length, best = 0;
    int[][] pre = new int[n + 1][m + 1];                    // pre[i][j] = ones in rows < i, cols < j
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) pre[i + 1][j + 1] = matrix[i][j] + pre[i][j + 1] + pre[i + 1][j] - pre[i][j];
    }
    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): about n^2 m^2 / 4 rectangles, each checked in O(1). For a 200 × 200 matrix that is roughly 4 × 10^8 checks, too slow. Space O(nm) for the prefix table.

The key reduction: one histogram per row

Fix the bottom row r of the rectangle. For each column j, let h[j] be the number of consecutive 1s in column j that end at row r (0 if matrix[r][j] is 0). Any all-ones rectangle with bottom row r that spans columns a..b can be at most min(h[a..b]) tall, and a rectangle of exactly that height fits, because every column in the range has at least that many ones stacked above row r.

So the best rectangle with bottom row r is the largest rectangle in the histogram h. Trying every bottom row covers every rectangle. And h is cheap to maintain, which is the DP part: going from row r - 1 to row r, a 1 extends the column (h[j] + 1) and a 0 resets it (0).

Heights for Example 1:

row 0:  1 0 1 0 0
row 1:  2 0 2 1 1
row 2:  3 1 3 2 2
row 3:  4 0 0 3 0

In row 2, the last three bars have heights 3, 2, 2, so a rectangle of height 2 and width 3 fits: area 6, the answer.

The remaining question is how fast we can solve one histogram. The next two approaches answer it in O(m^2) and O(m).

Approach 2: Better, extend each bar to the left

Intuition. For each column j taken as the right edge, walk left while the bars are non-zero, keeping the minimum height seen. A rectangle from k to j can be minH tall, so its area is minH · (j - k + 1). A zero bar stops the walk, since no rectangle can cross it.

Algorithm.

  1. For each row, update h.
  2. For each j, walk k from j down to 0 while h[k] > 0, update minH and the best area.
static int better(int[][] matrix) {
    int n = matrix.length, m = n == 0 ? 0 : matrix[0].length, best = 0;
    int[] h = new int[m];
    for (int[] row : matrix) {
        for (int j = 0; j < m; j++) h[j] = row[j] == 1 ? h[j] + 1 : 0;   // ones ending at this row
        for (int j = 0; j < m; j++) {                       // rectangle whose right edge is column j
            int minH = Integer.MAX_VALUE;
            for (int k = j; k >= 0 && h[k] > 0; k--) {
                minH = Math.min(minH, h[k]);
                best = Math.max(best, minH * (j - k + 1));
            }
        }
    }
    return best;
}

Complexity. Time O(n · m^2): O(m^2) pairs (k, j) per row. Space O(m) for h. That is about 8 × 10^6 steps for 200 × 200, which passes, but the histogram can be solved faster.

Approach 3: Optimal, monotonic stack

Intuition. In the best rectangle of a histogram, some bar is the shortest one inside it, and the rectangle uses that bar’s full height. So for every bar i, ask: how wide can a rectangle of height h[i] be? It extends left until the nearest bar shorter than h[i], and right until the nearest bar shorter than h[i]. The answer is the maximum of h[i] · width over all bars.

A stack of indices with increasing heights finds both boundaries in one pass. When the current bar cur is not taller than the bar on top of the stack, that top bar has found its right boundary: index i. After popping it, the new top is the nearest shorter bar to its left (or -1 if the stack is empty), because the stack only keeps strictly increasing heights. Its width is therefore i - left - 1. A sentinel bar of height 0 at i = m pops everything that is left.

Algorithm.

  1. For each row, update h and call largestInHistogram(h).
  2. In the helper, for i = 0 .. m with cur = h[i] (or 0 at the end): while the top bar is at least cur, pop it and compute its area; then push i.
static int optimal(int[][] matrix) {
    int n = matrix.length, m = n == 0 ? 0 : matrix[0].length, best = 0;
    int[] h = new int[m];
    for (int[] row : matrix) {
        for (int j = 0; j < m; j++) h[j] = row[j] == 1 ? h[j] + 1 : 0;
        best = Math.max(best, largestInHistogram(h));
    }
    return best;
}

static int largestInHistogram(int[] h) {
    int m = h.length, best = 0;
    Deque<Integer> stack = new ArrayDeque<>();              // indices of bars with increasing heights
    for (int i = 0; i <= m; i++) {
        int cur = i == m ? 0 : h[i];                        // a final bar of height 0 empties the stack
        while (!stack.isEmpty() && h[stack.peek()] >= cur) {
            int height = h[stack.pop()];
            int left = stack.isEmpty() ? -1 : stack.peek(); // nearest smaller bar on the left
            best = Math.max(best, height * (i - left - 1)); // i is the nearest smaller-or-equal on the right
        }
        stack.push(i);
    }
    return best;
}

Dry run of the helper on row 2 of Example 1, h = [3, 1, 3, 2, 2]:

i cur popped bar (height, left, width) area stack after
0 3     [0]
1 1 bar 0 (3, -1, 1) 3 [1]
2 3     [1, 2]
3 2 bar 2 (3, 1, 1) 3 [1, 3]
4 2 bar 3 (2, 1, 2) 4 [1, 4]
5 0 bar 4 (2, 1, 3), then bar 1 (1, -1, 5) 6, 5 [5]

Bar 3 is popped by an equal bar and gets too small a width (2 instead of 3). That is harmless: the last bar of a run of equal heights, bar 4, sees the full width and reports 6.

Complexity. Time O(nm): every index is pushed and popped at most once per row. Space O(m) for h and the stack.

Approach 4: Optimal without a stack

Intuition. Another O(nm) method keeps, for every column j, the rectangle of height h[j] that contains column j and is as wide as possible. Store its first column in left[j] and one past its last column in right[j]. All rows of that rectangle must have ones across [left[j], right[j]). Row r alone allows the run of ones containing j, say [curLeft, curRight). The rows above it allowed [left[j], right[j]) from the previous row. So the new limits are the intersection: left[j] = max(left[j], curLeft) and right[j] = min(right[j], curRight). When the cell is 0, the height becomes 0 and the limits reset to 0 and m, so the next row starts unconstrained.

Why this finds the optimum: take a best rectangle and its bottom row. It cannot be extended upward, so some column j inside it has a 0 just above its top edge (or the top edge is row 0). In that column h[j] equals the rectangle’s height, and the limits computed for j describe the widest band of that height around j, which is at least as wide as the rectangle. So height[j] · (right[j] - left[j]) is at least the optimal area.

Algorithm.

  1. Keep height, left (initially 0) and right (initially m) across rows.
  2. For each row: update height; sweep left to right to update left with curLeft; sweep right to left to update right with curRight.
  3. Update the answer with height[j] · (right[j] - left[j]) for every j.
static int optimalDp(int[][] matrix) {
    int n = matrix.length, m = n == 0 ? 0 : matrix[0].length, best = 0;
    int[] height = new int[m], left = new int[m], right = new int[m];
    Arrays.fill(right, m);
    for (int[] row : matrix) {
        int curLeft = 0, curRight = m;                      // boundaries of the current run of ones in this row
        for (int j = 0; j < m; j++) height[j] = row[j] == 1 ? height[j] + 1 : 0;
        for (int j = 0; j < m; j++) {
            if (row[j] == 1) left[j] = Math.max(left[j], curLeft);
            else { left[j] = 0; curLeft = j + 1; }
        }
        for (int j = m - 1; j >= 0; j--) {
            if (row[j] == 1) right[j] = Math.min(right[j], curRight);
            else { right[j] = m; curRight = j; }
        }
        for (int j = 0; j < m; j++) best = Math.max(best, height[j] * (right[j] - left[j]));
    }
    return best;
}

Complexity. Time O(nm) with three simple sweeps per row, space O(m). It does the same amount of work as the stack approach but with plain array scans.

Edge cases and pitfalls