Maximal Rectangle

hard array dp monotonic stack

Problem

Given a binary matrix of '0's and '1's, find the largest rectangle of '1's and return its area.

Process the matrix row by row. For each row, build a histogram: column j's bar height equals the number of consecutive 1's ending at row i. Then run the largest-rectangle-in-histogram routine (a monotonic increasing stack of indices) on that array. The overall answer is the max across all rows.

Inputmatrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

Output6

matrix (0/1, rows separated by ';')

def maximal_rectangle(matrix):
    if not matrix: return 0
    n = len(matrix[0])
    heights = [0] * n
    best = 0
    for row in matrix:
        for j in range(n):
            heights[j] = heights[j] + 1 if row[j] == "1" else 0
        best = max(best, largest_rectangle(heights))
    return best

def largest_rectangle(h):
    stack, best = [], 0
    for i in range(len(h) + 1):
        cur = 0 if i == len(h) else h[i]
        while stack and h[stack[-1]] > cur:
            top = stack.pop()
            width = i if not stack else i - stack[-1] - 1
            best = max(best, h[top] * width)
        stack.append(i)
    return best

function maximalRectangle(matrix) {
  if (!matrix.length) return 0;
  const n = matrix[0].length;
  const heights = new Array(n).fill(0);
  let best = 0;
  for (const row of matrix) {
    for (let j = 0; j < n; j++) heights[j] = row[j] === "1" ? heights[j] + 1 : 0;
    best = Math.max(best, largestRectangle(heights));
  }
  return best;
}

function largestRectangle(h) {
  const stack = []; let best = 0;
  for (let i = 0; i <= h.length; i++) {
    const cur = i === h.length ? 0 : h[i];
    while (stack.length && h[stack[stack.length - 1]] > cur) {
      const top = stack.pop();
      const width = stack.length ? i - stack[stack.length - 1] - 1 : i;
      best = Math.max(best, h[top] * width);
    }
    stack.push(i);
  }
  return best;
}

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) return 0;
        int n = matrix[0].length;
        int[] heights = new int[n];
        int best = 0;
        for (char[] row : matrix) {
            for (int j = 0; j < n; j++) heights[j] = row[j] == '1' ? heights[j] + 1 : 0;
            best = Math.max(best, largestRectangle(heights));
        }
        return best;
    }
    int largestRectangle(int[] h) {
        Deque<Integer> stack = new ArrayDeque<>();
        int best = 0;
        for (int i = 0; i <= h.length; i++) {
            int cur = i == h.length ? 0 : h[i];
            while (!stack.isEmpty() && h[stack.peek()] > cur) {
                int top = stack.pop();
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                best = Math.max(best, h[top] * width);
            }
            stack.push(i);
        }
        return best;
    }
}

int maximalRectangle(vector<vector<char>>& matrix) {
    if (matrix.empty()) return 0;
    int n = matrix[0].size();
    vector<int> heights(n, 0);
    int best = 0;
    for (auto& row : matrix) {
        for (int j = 0; j < n; j++) heights[j] = row[j] == '1' ? heights[j] + 1 : 0;
        best = max(best, largestRectangle(heights));
    }
    return best;
}
int largestRectangle(vector<int>& h) {
    stack<int> st; int best = 0;
    for (int i = 0; i <= (int)h.size(); i++) {
        int cur = i == (int)h.size() ? 0 : h[i];
        while (!st.empty() && h[st.top()] > cur) {
            int top = st.top(); st.pop();
            int width = st.empty() ? i : i - st.top() - 1;
            best = max(best, h[top] * width);
        }
        st.push(i);
    }
    return best;
}

Explanation

This 2D problem is solved by turning it into a series of 1D histogram problems. The key realization is that a rectangle of 1's in the matrix can be measured row by row by asking: for each column, how many 1's pile up directly above (and including) this row?

We keep a heights array, one entry per column. As we move down each row, if the cell is "1" we add one to that column's height; if it is "0" the streak breaks and the height resets to 0.

After updating heights for a row, we run the classic largest rectangle in a histogram routine on it, using a monotonic increasing stack of indices. We take the maximum area found across all rows.

The histogram helper pops a bar when a shorter bar appears, computing that bar's widest rectangle as h[top] * width, where width spans between the surrounding shorter bars.

Example: in the sample matrix, by the third row the column heights become [3, 1, 3, 2, 2], and the histogram routine finds a rectangle of area 6, which is the overall answer.

Time: O(m · n) Space: O(n)