Maximum size rectangle

The problem, simply

You get a grid of 0s and 1s with m rows and n columns. Find the biggest rectangle that holds only 1s, and give back its area (rows times columns).

The rectangle must have straight sides along the grid lines. It cannot bend around a 0.

A story to remember it

Picture it

Examples

Way 1: the simple way

Pretend each cell is the bottom right corner of a rectangle, and grow the rectangle upward.

1. For each cell, write down how many 1s in a row end at that cell, counting to the left. Call it run.
2. Stand on a cell (i, j). The rectangle can be run[i][j] wide. Climb up one row at a time. The width shrinks to the smallest run you have passed, like a ruler that can only get shorter.
3. At each step the area is width times the number of rows climbed. Keep the best.

class Solution {
    public int maximalRectangle(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return 0;
        int m = matrix.length, n = matrix[0].length;
        int[][] run = new int[m][n];        // 1s in a row that end at this cell
        int best = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) run[i][j] = (j > 0 ? run[i][j - 1] : 0) + 1;

                int width = run[i][j];     // (i, j) is the bottom right corner
                for (int k = i; k >= 0 && width > 0; k--) {     // climb up
                    width = Math.min(width, run[k][j]);        // the ruler only shrinks
                    best = Math.max(best, width * (i - k + 1));
                }
            }
        }
        return best;
    }
}

How long it takes: for each of the m * n cells we may climb up to m rows, O(m^2*n). Extra room: the run table, O(m*n). Checking every possible rectangle from scratch would be far worse, about O(m^3*n^3).

Way 2: the clever way

Use the floor and towers idea. Keep one array heights with one tower per column.

1. For each row, update the towers: if the cell is 1, the tower grows by one; if it is 0, the tower falls to 0.

1. Find the biggest rectangle in this skyline. This is its own classic problem (largest rectangle in a histogram), solved with a stack:
   • Walk the towers left to right. The stack holds column numbers, and their towers get taller from the bottom of the stack to the top.
   • When the current tower is shorter than the tower on top of the stack, the top tower cannot stretch any further right. Pop it. It stretches left to just after the new top of the stack, and right to just before the current column. Measure its area.
   • Push the current column.
   • At the end, pretend there is a tower of height 0, so every tower left in the stack gets popped and measured.
2. The best area over all rows is the answer.

import java.util.*;

class Solution {
    public int maximalRectangle(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return 0;
        int n = matrix[0].length;
        int[] heights = new int[n];
        int best = 0;

        for (int[] row : matrix) {
            for (int j = 0; j < n; j++) {
                heights[j] = row[j] == 1 ? heights[j] + 1 : 0;   // grow the tower, or knock it down
            }
            best = Math.max(best, largestInSkyline(heights));
        }
        return best;
    }

    private int largestInSkyline(int[] heights) {
        int n = heights.length, best = 0;
        Deque<Integer> stack = new ArrayDeque<>();   // columns with towers growing taller toward the top
        for (int i = 0; i <= n; i++) {
            int h = (i == n) ? 0 : heights[i];       // a pretend tower of height 0 at the end
            while (!stack.isEmpty() && h < heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int left = stack.isEmpty() ? 0 : stack.peek() + 1;   // stretches left to here
                int width = i - left;                                // and right to i - 1
                best = Math.max(best, height * width);
            }
            stack.push(i);
        }
        return best;
    }
}

How long it takes: for each of the m rows we update n towers and run the stack once. Each column is pushed once and popped once, so a row costs O(n). Total O(m*n). Extra room: the heights array and the stack, O(n).

Watch out for

• Not resetting a tower to 0 on a 0 cell. A tower must stand on an unbroken column of 1s.
• Width when the stack is empty after a pop: the tower stretches all the way to the left edge, so the width is i, not i - 1.
• char input. On LeetCode the grid is char[][] with '0' and '1'. Compare with '1', not with 1.
• Equal heights. Popping only on strictly shorter towers is fine: the first of the equal towers still gets the full width when it is popped.

What interviewers ask next

• Biggest square of 1s instead? Use a simpler table: size[i][j] = 1 + min(top, left, top left) when the cell is 1. O(m*n) time.
• Largest rectangle in a histogram on its own? That is the helper above, and it is a common interview question by itself.
• Count all rectangles made only of 1s (count submatrices with all ones). Use the same towers, and a stack that adds up how many rectangles end at each column.
• Can you do it without a stack? Yes. For each row keep three arrays: height, left (how far a tower of that height can stretch left) and right. Update them row by row. Same O(m*n) time.
• What if the grid is very tall and narrow? Build the towers along the shorter side, so the stack work is O(min(m, n)) room.

Remember this

Grown-up words: the towers are a histogram of heights, the rising stack is a monotonic stack, the left and right walls of a popped tower are the previous and next smaller elements, and the whole problem is called Maximal Rectangle.