#81 · Stack

Maximal Rectangle

Given a rows × cols binary matrix filled with 0s and 1s, find the largest rectangle containing only 1s and return its area.

HardLeetCode

Computing
Depends on
Answer

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Per-row histogram

Process the matrix one row at a time and keep heights[c], the number of consecutive 1s ending at the current row in column c. Every all-ones rectangle whose bottom edge is on this row is a rectangle inside that histogram.

Memory layout

One array of cols numbers reused for every row, updated in place.

Operation	Cost
update per row	O(cols)

Monotonic stack (from Largest Rectangle in Histogram)

Solves each row's histogram in linear time by measuring a bar when a shorter bar arrives to its right.

Memory layout

A stack of at most cols + 1 column indices per row.

Operation	Cost
per row	O(cols) amortised

height / left / right DP arrays

For every column keep how tall the bar is and how far left and right a rectangle of that height can stretch. left and right only tighten as long as the column keeps its ones.

Memory layout

Three arrays of cols numbers.

Operation	Cost
per row	O(cols)

Why it fits

The 2-D problem is "largest rectangle in histogram" repeated once per row, so a proven 1-D tool applies directly.
Heights are cumulative, so moving to the next row is an O(cols) update, not a rebuild.
The DP-array variant carries left and right from row to row: while a column keeps its ones, the left bound of its rectangle can only move right and the right bound only left, so previous values are a valid starting point.

Why alternatives degrade

Brute force over all rectangles:: O((m·n)²) corners times a validity check: too slow for 200 × 200.
2-D prefix sums to test rectangles:: Checking validity is O(1), but enumerating all rectangles is still O(m²·n²).
Union-find on connected 1s:: Connected components are not rectangles: an L-shape is connected but not a rectangle.

Four approaches, from naive to production

1 · beginner

Grow a rectangle from every top-left corner

time O(rows² · cols²)space O(1)

For each cell containing 1, grow downwards row by row, tracking the narrowest run of 1s to the right. Each extension is a candidate rectangle.

int maximalRectangle(vector<vector<char>>& matrix) {
    int rows = matrix.size(), cols = rows == 0 ? 0 : matrix[0].size();
    int best = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (matrix[r][c] == '0') continue;
            int minWidth = cols - c;
            for (int r2 = r; r2 < rows && matrix[r2][c] == '1'; r2++) {
                int w = 0;
                while (c + w < cols && w < minWidth && matrix[r2][c + w] == '1') w++;
                minWidth = min(minWidth, w);
                best = max(best, minWidth * (r2 - r + 1));
            }
        }
    }
    return best;
}

public int maximalRectangle(char[][] matrix) {
    int rows = matrix.length, cols = rows == 0 ? 0 : matrix[0].length;
    int best = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (matrix[r][c] == '0') continue;
            int minWidth = cols - c;
            for (int r2 = r; r2 < rows && matrix[r2][c] == '1'; r2++) {
                int w = 0;
                while (c + w < cols && w < minWidth && matrix[r2][c + w] == '1') w++;
                minWidth = Math.min(minWidth, w);
                best = Math.max(best, minWidth * (r2 - r + 1));
            }
        }
    }
    return best;
}

def maximal_rectangle(matrix):
    rows = len(matrix); cols = len(matrix[0]) if rows else 0
    best = 0
    for r in range(rows):
        for c in range(cols):
            if matrix[r][c] == '0': continue
            min_width = cols - c
            r2 = r
            while r2 < rows and matrix[r2][c] == '1':
                w = 0
                while c + w < cols and w < min_width and matrix[r2][c + w] == '1': w += 1
                min_width = min(min_width, w)
                best = max(best, min_width * (r2 - r + 1))
                r2 += 1
    return best

function maximalRectangle(matrix: string[][]): number {
  const rows = matrix.length, cols = rows === 0 ? 0 : matrix[0].length;
  let best = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (matrix[r][c] === '0') continue;
      let minWidth = cols - c;
      for (let r2 = r; r2 < rows && matrix[r2][c] === '1'; r2++) {
        let w = 0;
        while (c + w < cols && w < minWidth && matrix[r2][c + w] === '1') w++;
        minWidth = Math.min(minWidth, w);
        best = Math.max(best, minWidth * (r2 - r + 1));
      }
    }
  }
  return best;
}

Flaws & bottlenecks

Rescans the same runs for every corner.
Quartic in the worst case (an all-ones matrix).
No reuse between neighbouring rows or columns.

Interviewer cross-questions

Why track a minimum width?

Say: A rectangle must be as wide as its narrowest row, so each added row can only shrink the usable width.

Is every optimal rectangle found?

Say: Yes: its top-left corner is one of the cells tried, and growing down from it considers every height.

How can you avoid recomputing runs?

Say: Precompute, for each cell, how many consecutive 1s lie above (or to the right): that is the histogram idea.

2 · intermediate

Histogram per row, try every left and right

time O(rows · cols²)space O(cols)

Keep column heights that grow with consecutive 1s. For each row, try every left edge and extend right while tracking the minimum height.

int maximalRectangle(vector<vector<char>>& matrix) {
    int rows = matrix.size(), cols = rows == 0 ? 0 : matrix[0].size();
    vector<int> heights(cols, 0);
    int best = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) heights[c] = matrix[r][c] == '1' ? heights[c] + 1 : 0;
        for (int left = 0; left < cols; left++) {
            int minH = heights[left];
            for (int right = left; right < cols && minH > 0; right++) {
                minH = min(minH, heights[right]);
                best = max(best, minH * (right - left + 1));
            }
        }
    }
    return best;
}

public int maximalRectangle(char[][] matrix) {
    int rows = matrix.length, cols = rows == 0 ? 0 : matrix[0].length;
    int[] heights = new int[cols];
    int best = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) heights[c] = matrix[r][c] == '1' ? heights[c] + 1 : 0;
        for (int left = 0; left < cols; left++) {
            int minH = heights[left];
            for (int right = left; right < cols && minH > 0; right++) {
                minH = Math.min(minH, heights[right]);
                best = Math.max(best, minH * (right - left + 1));
            }
        }
    }
    return best;
}

def maximal_rectangle(matrix):
    rows = len(matrix); cols = len(matrix[0]) if rows else 0
    heights = [0] * cols
    best = 0
    for r in range(rows):
        for c in range(cols): heights[c] = heights[c] + 1 if matrix[r][c] == '1' else 0
        for left in range(cols):
            min_h = heights[left]
            right = left
            while right < cols and min_h > 0:
                min_h = min(min_h, heights[right])
                best = max(best, min_h * (right - left + 1))
                right += 1
    return best

function maximalRectangle(matrix: string[][]): number {
  const rows = matrix.length, cols = rows === 0 ? 0 : matrix[0].length;
  const heights = new Array<number>(cols).fill(0);
  let best = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) heights[c] = matrix[r][c] === '1' ? heights[c] + 1 : 0;
    for (let left = 0; left < cols; left++) {
      let minH = heights[left];
      for (let right = left; right < cols && minH > 0; right++) {
        minH = Math.min(minH, heights[right]);
        best = Math.max(best, minH * (right - left + 1));
      }
    }
  }
  return best;
}

Flaws & bottlenecks

Quadratic in the number of columns per row.
Re-derives the nearest shorter bars that a stack finds in linear time.
Early exit on a zero height helps only on sparse rows.

Interviewer cross-questions

Why does a rectangle ending at this row correspond to a histogram rectangle?

Say: Its columns each have at least that many consecutive 1s ending here, which is exactly what heights stores.

Which dimension should be the histogram axis?

Say: Either works. Choosing the smaller dimension for the columns cuts the per-row cost and the extra memory.

How do you make each row linear?

Say: Replace the pair loop with the monotonic stack from Largest Rectangle in Histogram.

3 · advanced

Monotonic stack on each row's histogram

time O(rows · cols)space O(cols)

Update heights in place for the row, then run the one-pass stack algorithm over heights (with a zero sentinel) to find the best rectangle ending on that row.

int maximalRectangle(vector<vector<char>>& matrix) {
    int rows = matrix.size();
    if (rows == 0) return 0;
    int cols = matrix[0].size();
    vector<int> heights(cols + 1, 0);
    int best = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) heights[c] = matrix[r][c] == '1' ? heights[c] + 1 : 0;
        vector<int> stack;
        for (int i = 0; i <= cols; i++) {
            while (!stack.empty() && heights[stack.back()] >= heights[i]) {
                int h = heights[stack.back()]; stack.pop_back();
                int left = stack.empty() ? -1 : stack.back();
                best = max(best, h * (i - left - 1));
            }
            stack.push_back(i);
        }
    }
    return best;
}

public int maximalRectangle(char[][] matrix) {
    int rows = matrix.length;
    if (rows == 0) return 0;
    int cols = matrix[0].length;
    int[] heights = new int[cols + 1];
    int best = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) heights[c] = matrix[r][c] == '1' ? heights[c] + 1 : 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i <= cols; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                int h = heights[stack.pop()];
                int left = stack.isEmpty() ? -1 : stack.peek();
                best = Math.max(best, h * (i - left - 1));
            }
            stack.push(i);
        }
    }
    return best;
}

def maximal_rectangle(matrix):
    rows = len(matrix)
    if rows == 0: return 0
    cols = len(matrix[0])
    heights = [0] * (cols + 1)
    best = 0
    for r in range(rows):
        for c in range(cols): heights[c] = heights[c] + 1 if matrix[r][c] == '1' else 0
        stack = []
        for i in range(cols + 1):
            while stack and heights[stack[-1]] >= heights[i]:
                h = heights[stack.pop()]
                left = stack[-1] if stack else -1
                best = max(best, h * (i - left - 1))
            stack.append(i)
    return best

function maximalRectangle(matrix: string[][]): number {
  const rows = matrix.length;
  if (rows === 0) return 0;
  const cols = matrix[0].length;
  const heights = new Array<number>(cols + 1).fill(0);
  let best = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) heights[c] = matrix[r][c] === '1' ? heights[c] + 1 : 0;
    const stack: number[] = [];
    for (let i = 0; i <= cols; i++) {
      while (stack.length > 0 && heights[stack[stack.length - 1]] >= heights[i]) {
        const h = heights[stack.pop()!];
        const left = stack.length === 0 ? -1 : stack[stack.length - 1];
        best = Math.max(best, h * (i - left - 1));
      }
      stack.push(i);
    }
  }
  return best;
}

Flaws & bottlenecks

Needs the histogram problem understood first.
A fresh stack per row (or a cleared one) is easy to misuse.
The sentinel slot and index arithmetic are error prone.

Interviewer cross-questions

What is the total complexity?

Say: rows × O(cols): each row's stack pass is linear since every column is pushed and popped once.

Why is heights one slot longer?

Say: The extra slot is a permanent 0 sentinel that pops every bar left on the stack at the end of the row.

What if the matrix holds characters, not ints?

Say: Compare against the character '1', as here; it avoids a conversion pass.

4 · expert

Height / left / right DP (no stack)

time O(rows · cols)space O(cols)

Per column keep height, left bound and right bound. Each row updates height, tightens left on a left-to-right pass and right on a right-to-left pass, then scores (right − left) × height.

int maximalRectangle(vector<vector<char>>& matrix) {
    int rows = matrix.size();
    if (rows == 0 || matrix[0].empty()) return 0;
    int cols = matrix[0].size();
    vector<int> height(cols, 0);
    vector<int> left(cols, 0);
    vector<int> right(cols, cols);
    int best = 0;
    for (int r = 0; r < rows; r++) {
        int curLeft = 0, curRight = cols;
        for (int c = 0; c < cols; c++) height[c] = matrix[r][c] == '1' ? height[c] + 1 : 0;
        for (int c = 0; c < cols; c++) {
            if (matrix[r][c] == '1') left[c] = max(left[c], curLeft);
            else { left[c] = 0; curLeft = c + 1; }
        }
        for (int c = cols - 1; c >= 0; c--) {
            if (matrix[r][c] == '1') right[c] = min(right[c], curRight);
            else { right[c] = cols; curRight = c; }
        }
        for (int c = 0; c < cols; c++) best = max(best, (right[c] - left[c]) * height[c]);
    }
    return best;
}

public int maximalRectangle(char[][] matrix) {
    int rows = matrix.length;
    if (rows == 0 || matrix[0].length == 0) return 0;
    int cols = matrix[0].length;
    int[] height = new int[cols];
    int[] left = new int[cols];
    int[] right = new int[cols]; Arrays.fill(right, cols);
    int best = 0;
    for (int r = 0; r < rows; r++) {
        int curLeft = 0, curRight = cols;
        for (int c = 0; c < cols; c++) height[c] = matrix[r][c] == '1' ? height[c] + 1 : 0;
        for (int c = 0; c < cols; c++) {
            if (matrix[r][c] == '1') left[c] = Math.max(left[c], curLeft);
            else { left[c] = 0; curLeft = c + 1; }
        }
        for (int c = cols - 1; c >= 0; c--) {
            if (matrix[r][c] == '1') right[c] = Math.min(right[c], curRight);
            else { right[c] = cols; curRight = c; }
        }
        for (int c = 0; c < cols; c++) best = Math.max(best, (right[c] - left[c]) * height[c]);
    }
    return best;
}

def maximal_rectangle(matrix):
    rows = len(matrix)
    if rows == 0 or len(matrix[0]) == 0: return 0
    cols = len(matrix[0])
    height = [0] * cols
    left = [0] * cols
    right = [cols] * cols
    best = 0
    for r in range(rows):
        cur_left, cur_right = 0, cols
        for c in range(cols): height[c] = height[c] + 1 if matrix[r][c] == '1' else 0
        for c in range(cols):
            if matrix[r][c] == '1': left[c] = max(left[c], cur_left)
            else: left[c] = 0; cur_left = c + 1
        for c in range(cols - 1, -1, -1):
            if matrix[r][c] == '1': right[c] = min(right[c], cur_right)
            else: right[c] = cols; cur_right = c
        for c in range(cols): best = max(best, (right[c] - left[c]) * height[c])
    return best

function maximalRectangle(matrix: string[][]): number {
  const rows = matrix.length;
  if (rows === 0 || matrix[0].length === 0) return 0;
  const cols = matrix[0].length;
  const height = new Array<number>(cols).fill(0);
  const left = new Array<number>(cols).fill(0);
  const right = new Array<number>(cols).fill(cols);
  let best = 0;
  for (let r = 0; r < rows; r++) {
    let curLeft = 0, curRight = cols;
    for (let c = 0; c < cols; c++) height[c] = matrix[r][c] === '1' ? height[c] + 1 : 0;
    for (let c = 0; c < cols; c++) {
      if (matrix[r][c] === '1') left[c] = Math.max(left[c], curLeft);
      else { left[c] = 0; curLeft = c + 1; }
    }
    for (let c = cols - 1; c >= 0; c--) {
      if (matrix[r][c] === '1') right[c] = Math.min(right[c], curRight);
      else { right[c] = cols; curRight = c; }
    }
    for (let c = 0; c < cols; c++) best = Math.max(best, (right[c] - left[c]) * height[c]);
  }
  return best;
}

Flaws & bottlenecks

The left / right invariants are subtle and hard to derive during an interview.
Resetting left = 0 and right = cols for a 0 cell must be done at the right moment.
Four passes per row; the stack version does about two.

Interviewer cross-questions

Why can left carry over from the previous row?

Say: If a column kept its ones, the rectangle of its height from the previous row is still valid, so its left bound can only move right (tighten) when this row has a 0 to the left.

What does left = 0 mean for a zero cell?

Say: A zero column has height 0, so it contributes no area; resetting its bounds lets later rows start fresh there.

What are the boundary cases?

Say: Empty matrix, one empty row, a single cell, all zeros (0) and all ones (rows × cols).

Synchronized code walkthrough

Showing: Grow a rectangle from every top-left corner — shares the player above; click any step to jump.

int maximalRectangle(vector<vector<char>>& matrix) {
    int rows = matrix.size(), cols = rows == 0 ? 0 : matrix[0].size();
    int best = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (matrix[r][c] == '0') continue;
            int minWidth = cols - c;
            for (int r2 = r; r2 < rows && matrix[r2][c] == '1'; r2++) {
                int w = 0;
                while (c + w < cols && w < minWidth && matrix[r2][c + w] == '1') w++;
                minWidth = min(minWidth, w);
                best = max(best, minWidth * (r2 - r + 1));
            }
        }
    }
    return best;
}

public int maximalRectangle(char[][] matrix) {
    int rows = matrix.length, cols = rows == 0 ? 0 : matrix[0].length;
    int best = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (matrix[r][c] == '0') continue;
            int minWidth = cols - c;
            for (int r2 = r; r2 < rows && matrix[r2][c] == '1'; r2++) {
                int w = 0;
                while (c + w < cols && w < minWidth && matrix[r2][c + w] == '1') w++;
                minWidth = Math.min(minWidth, w);
                best = Math.max(best, minWidth * (r2 - r + 1));
            }
        }
    }
    return best;
}

def maximal_rectangle(matrix):
    rows = len(matrix); cols = len(matrix[0]) if rows else 0
    best = 0
    for r in range(rows):
        for c in range(cols):
            if matrix[r][c] == '0': continue
            min_width = cols - c
            r2 = r
            while r2 < rows and matrix[r2][c] == '1':
                w = 0
                while c + w < cols and w < min_width and matrix[r2][c + w] == '1': w += 1
                min_width = min(min_width, w)
                best = max(best, min_width * (r2 - r + 1))
                r2 += 1
    return best

function maximalRectangle(matrix: string[][]): number {
  const rows = matrix.length, cols = rows === 0 ? 0 : matrix[0].length;
  let best = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (matrix[r][c] === '0') continue;
      let minWidth = cols - c;
      for (let r2 = r; r2 < rows && matrix[r2][c] === '1'; r2++) {
        let w = 0;
        while (c + w < cols && w < minWidth && matrix[r2][c + w] === '1') w++;
        minWidth = Math.min(minWidth, w);
        best = Math.max(best, minWidth * (r2 - r + 1));
      }
    }
  }
  return best;
}

int maximalRectangle(vector<vector<char>>& matrix) {
    int rows = matrix.size(), cols = rows == 0 ? 0 : matrix[0].size();
    vector<int> heights(cols, 0);
    int best = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) heights[c] = matrix[r][c] == '1' ? heights[c] + 1 : 0;
        for (int left = 0; left < cols; left++) {
            int minH = heights[left];
            for (int right = left; right < cols && minH > 0; right++) {
                minH = min(minH, heights[right]);
                best = max(best, minH * (right - left + 1));
            }
        }
    }
    return best;
}

public int maximalRectangle(char[][] matrix) {
    int rows = matrix.length, cols = rows == 0 ? 0 : matrix[0].length;
    int[] heights = new int[cols];
    int best = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) heights[c] = matrix[r][c] == '1' ? heights[c] + 1 : 0;
        for (int left = 0; left < cols; left++) {
            int minH = heights[left];
            for (int right = left; right < cols && minH > 0; right++) {
                minH = Math.min(minH, heights[right]);
                best = Math.max(best, minH * (right - left + 1));
            }
        }
    }
    return best;
}

def maximal_rectangle(matrix):
    rows = len(matrix); cols = len(matrix[0]) if rows else 0
    heights = [0] * cols
    best = 0
    for r in range(rows):
        for c in range(cols): heights[c] = heights[c] + 1 if matrix[r][c] == '1' else 0
        for left in range(cols):
            min_h = heights[left]
            right = left
            while right < cols and min_h > 0:
                min_h = min(min_h, heights[right])
                best = max(best, min_h * (right - left + 1))
                right += 1
    return best

function maximalRectangle(matrix: string[][]): number {
  const rows = matrix.length, cols = rows === 0 ? 0 : matrix[0].length;
  const heights = new Array<number>(cols).fill(0);
  let best = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) heights[c] = matrix[r][c] === '1' ? heights[c] + 1 : 0;
    for (let left = 0; left < cols; left++) {
      let minH = heights[left];
      for (let right = left; right < cols && minH > 0; right++) {
        minH = Math.min(minH, heights[right]);
        best = Math.max(best, minH * (right - left + 1));
      }
    }
  }
  return best;
}

int maximalRectangle(vector<vector<char>>& matrix) {
    int rows = matrix.size();
    if (rows == 0) return 0;
    int cols = matrix[0].size();
    vector<int> heights(cols + 1, 0);
    int best = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) heights[c] = matrix[r][c] == '1' ? heights[c] + 1 : 0;
        vector<int> stack;
        for (int i = 0; i <= cols; i++) {
            while (!stack.empty() && heights[stack.back()] >= heights[i]) {
                int h = heights[stack.back()]; stack.pop_back();
                int left = stack.empty() ? -1 : stack.back();
                best = max(best, h * (i - left - 1));
            }
            stack.push_back(i);
        }
    }
    return best;
}

public int maximalRectangle(char[][] matrix) {
    int rows = matrix.length;
    if (rows == 0) return 0;
    int cols = matrix[0].length;
    int[] heights = new int[cols + 1];
    int best = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) heights[c] = matrix[r][c] == '1' ? heights[c] + 1 : 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i <= cols; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                int h = heights[stack.pop()];
                int left = stack.isEmpty() ? -1 : stack.peek();
                best = Math.max(best, h * (i - left - 1));
            }
            stack.push(i);
        }
    }
    return best;
}

def maximal_rectangle(matrix):
    rows = len(matrix)
    if rows == 0: return 0
    cols = len(matrix[0])
    heights = [0] * (cols + 1)
    best = 0
    for r in range(rows):
        for c in range(cols): heights[c] = heights[c] + 1 if matrix[r][c] == '1' else 0
        stack = []
        for i in range(cols + 1):
            while stack and heights[stack[-1]] >= heights[i]:
                h = heights[stack.pop()]
                left = stack[-1] if stack else -1
                best = max(best, h * (i - left - 1))
            stack.append(i)
    return best

function maximalRectangle(matrix: string[][]): number {
  const rows = matrix.length;
  if (rows === 0) return 0;
  const cols = matrix[0].length;
  const heights = new Array<number>(cols + 1).fill(0);
  let best = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) heights[c] = matrix[r][c] === '1' ? heights[c] + 1 : 0;
    const stack: number[] = [];
    for (let i = 0; i <= cols; i++) {
      while (stack.length > 0 && heights[stack[stack.length - 1]] >= heights[i]) {
        const h = heights[stack.pop()!];
        const left = stack.length === 0 ? -1 : stack[stack.length - 1];
        best = Math.max(best, h * (i - left - 1));
      }
      stack.push(i);
    }
  }
  return best;
}

int maximalRectangle(vector<vector<char>>& matrix) {
    int rows = matrix.size();
    if (rows == 0 || matrix[0].empty()) return 0;
    int cols = matrix[0].size();
    vector<int> height(cols, 0);
    vector<int> left(cols, 0);
    vector<int> right(cols, cols);
    int best = 0;
    for (int r = 0; r < rows; r++) {
        int curLeft = 0, curRight = cols;
        for (int c = 0; c < cols; c++) height[c] = matrix[r][c] == '1' ? height[c] + 1 : 0;
        for (int c = 0; c < cols; c++) {
            if (matrix[r][c] == '1') left[c] = max(left[c], curLeft);
            else { left[c] = 0; curLeft = c + 1; }
        }
        for (int c = cols - 1; c >= 0; c--) {
            if (matrix[r][c] == '1') right[c] = min(right[c], curRight);
            else { right[c] = cols; curRight = c; }
        }
        for (int c = 0; c < cols; c++) best = max(best, (right[c] - left[c]) * height[c]);
    }
    return best;
}

public int maximalRectangle(char[][] matrix) {
    int rows = matrix.length;
    if (rows == 0 || matrix[0].length == 0) return 0;
    int cols = matrix[0].length;
    int[] height = new int[cols];
    int[] left = new int[cols];
    int[] right = new int[cols]; Arrays.fill(right, cols);
    int best = 0;
    for (int r = 0; r < rows; r++) {
        int curLeft = 0, curRight = cols;
        for (int c = 0; c < cols; c++) height[c] = matrix[r][c] == '1' ? height[c] + 1 : 0;
        for (int c = 0; c < cols; c++) {
            if (matrix[r][c] == '1') left[c] = Math.max(left[c], curLeft);
            else { left[c] = 0; curLeft = c + 1; }
        }
        for (int c = cols - 1; c >= 0; c--) {
            if (matrix[r][c] == '1') right[c] = Math.min(right[c], curRight);
            else { right[c] = cols; curRight = c; }
        }
        for (int c = 0; c < cols; c++) best = Math.max(best, (right[c] - left[c]) * height[c]);
    }
    return best;
}

def maximal_rectangle(matrix):
    rows = len(matrix)
    if rows == 0 or len(matrix[0]) == 0: return 0
    cols = len(matrix[0])
    height = [0] * cols
    left = [0] * cols
    right = [cols] * cols
    best = 0
    for r in range(rows):
        cur_left, cur_right = 0, cols
        for c in range(cols): height[c] = height[c] + 1 if matrix[r][c] == '1' else 0
        for c in range(cols):
            if matrix[r][c] == '1': left[c] = max(left[c], cur_left)
            else: left[c] = 0; cur_left = c + 1
        for c in range(cols - 1, -1, -1):
            if matrix[r][c] == '1': right[c] = min(right[c], cur_right)
            else: right[c] = cols; cur_right = c
        for c in range(cols): best = max(best, (right[c] - left[c]) * height[c])
    return best

function maximalRectangle(matrix: string[][]): number {
  const rows = matrix.length;
  if (rows === 0 || matrix[0].length === 0) return 0;
  const cols = matrix[0].length;
  const height = new Array<number>(cols).fill(0);
  const left = new Array<number>(cols).fill(0);
  const right = new Array<number>(cols).fill(cols);
  let best = 0;
  for (let r = 0; r < rows; r++) {
    let curLeft = 0, curRight = cols;
    for (let c = 0; c < cols; c++) height[c] = matrix[r][c] === '1' ? height[c] + 1 : 0;
    for (let c = 0; c < cols; c++) {
      if (matrix[r][c] === '1') left[c] = Math.max(left[c], curLeft);
      else { left[c] = 0; curLeft = c + 1; }
    }
    for (let c = cols - 1; c >= 0; c--) {
      if (matrix[r][c] === '1') right[c] = Math.min(right[c], curRight);
      else { right[c] = cols; curRight = c; }
    }
    for (let c = 0; c < cols; c++) best = Math.max(best, (right[c] - left[c]) * height[c]);
  }
  return best;
}