Maximal Rectangle

import java.util.*;

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 c = 0; c < n; c++) {
                heights[c] = (row[c] == '1') ? heights[c] + 1 : 0;
            }
            best = Math.max(best, largestRectangleArea(heights));
        }
        return best;
    }

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

func maximalRectangle(matrix [][]byte) int {
    if len(matrix) == 0 {
        return 0
    }
    n := len(matrix[0])
    heights := make([]int, n)
    best := 0

    for _, row := range matrix {
        for c := 0; c < n; c++ {
            if row[c] == '1' {
                heights[c]++
            } else {
                heights[c] = 0
            }
        }
        area := largestRect(heights)
        if area > best {
            best = area
        }
    }
    return best
}

func largestRect(heights []int) int {
    stack := []int{}
    best := 0
    for i := 0; i <= len(heights); i++ {
        h := 0
        if i < len(heights) {
            h = heights[i]
        }
        for len(stack) > 0 && heights[stack[len(stack)-1]] > h {
            idx := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            left := -1
            if len(stack) > 0 {
                left = stack[len(stack)-1]
            }
            width := i - left - 1
            area := heights[idx] * width
            if area > best {
                best = area
            }
        }
        stack = append(stack, i)
    }
    return best
}

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0

        n = len(matrix[0])
        heights = [0] * n
        best = 0

        for row in matrix:
            for c in range(n):
                heights[c] = heights[c] + 1 if row[c] == '1' else 0
            best = max(best, self._largest_rectangle(heights))

        return best

    def _largest_rectangle(self, heights: List[int]) -> int:
        stack = []
        best = 0
        for i in range(len(heights) + 1):
            h = 0 if i == len(heights) else heights[i]
            while stack and heights[stack[-1]] > h:
                idx = stack.pop()
                left = stack[-1] if stack else -1
                width = i - left - 1
                best = max(best, heights[idx] * width)
            stack.append(i)
        return best

impl Solution {
    pub fn maximal_rectangle(matrix: Vec<Vec<char>>) -> i32 {
        if matrix.is_empty() {
            return 0;
        }
        let n = matrix[0].len();
        let mut heights = vec![0; n];
        let mut best = 0;

        for row in matrix {
            for c in 0..n {
                heights[c] = if row[c] == '1' { heights[c] + 1 } else { 0 };
            }
            best = best.max(largest_rect(&heights));
        }
        best
    }
}

fn largest_rect(heights: &Vec<i32>) -> i32 {
    let mut stack: Vec<usize> = Vec::new();
    let mut best = 0;
    for i in 0..=heights.len() {
        let h = if i == heights.len() { 0 } else { heights[i] };
        while let Some(&top) = stack.last() {
            if heights[top] <= h {
                break;
            }
            let idx = stack.pop().unwrap();
            let left = stack.last().copied().map(|x| x as i32).unwrap_or(-1);
            let width = i as i32 - left - 1;
            best = best.max(heights[idx] * width);
        }
        stack.push(i);
    }
    best
}

function maximalRectangle(matrix: string[][]): number {
  if (matrix.length === 0) return 0;
  const n = matrix[0].length;
  const heights: number[] = Array(n).fill(0);
  let best = 0;

  const largestRect = (arr: number[]): number => {
    const stack: number[] = [];
    let ans = 0;
    for (let i = 0; i <= arr.length; i++) {
      const h = i === arr.length ? 0 : arr[i];
      while (stack.length && arr[stack[stack.length - 1]] > h) {
        const idx = stack.pop()!;
        const left = stack.length ? stack[stack.length - 1] : -1;
        const width = i - left - 1;
        ans = Math.max(ans, arr[idx] * width);
      }
      stack.push(i);
    }
    return ans;
  };

  for (const row of matrix) {
    for (let c = 0; c < n; c++) {
      heights[c] = row[c] === '1' ? heights[c] + 1 : 0;
    }
    best = Math.max(best, largestRect(heights));
  }

  return best;
}