Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Monotonic Stack

Guide 2 of 6 · Path 2 of 6

← PreviousNext →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Hardmonotonic-stack

Maximal Rectangle

Problem (restated)

Binary matrix of ‘0’/‘1’. Return the area of the largest rectangle containing only 1s.

Intuition

Treat each row as the base of a histogram: heights[c] = consecutive 1s upward. Largest rectangle in histogram (monotonic stack) per row; take max.

Approaches

Histogram per row + stack

Tested only
Time O(mn)Space O(n)

Idea. Reset height on ‘0’. Same stack template as LC84.

Walkthrough. A block of ones spanning 2×3 → area 6 when the bottom row sees heights [2,2,2].

Trade-offs. DP left/right/up also O(mn); stack reuses LC84.

Solution
export function maximalRectangle(matrix: string[][]): number {
  if (!matrix.length || !matrix[0]!.length) return 0;
  const m = matrix.length, n = matrix[0]!.length;
  const heights = Array(n).fill(0);
  let best = 0;
  const largestRectangle = (h: number[]): number => {
    const stack: number[] = [];
    let ans = 0;
    for (let i = 0; i <= h.length; i++) {
      const cur = i === h.length ? 0 : h[i]!;
      while (stack.length && cur < h[stack[stack.length - 1]!]!) {
        const height = h[stack.pop()!]!;
        const left = stack.length ? stack[stack.length - 1]! : -1;
        ans = Math.max(ans, height * (i - left - 1));
      }
      stack.push(i);
    }
    return ans;
  };
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) heights[c] = matrix[r]![c] === "1" ? heights[c]! + 1 : 0;
    best = Math.max(best, largestRectangle(heights));
  }
  return best;
}

export function maximalRectangle(matrix: string[][]): number {
  if (!matrix.length || !matrix[0]!.length) return 0;
  const m = matrix.length, n = matrix[0]!.length;
  const heights = Array(n).fill(0);
  let best = 0;
  const largestRectangle = (h: number[]): number => {
    const stack: number[] = [];
    let ans = 0;
    for (let i = 0; i <= h.length; i++) {
      const cur = i === h.length ? 0 : h[i]!;
      while (stack.length && cur < h[stack[stack.length - 1]!]!) {
        const height = h[stack.pop()!]!;
        const left = stack.length ? stack[stack.length - 1]! : -1;
        ans = Math.max(ans, height * (i - left - 1));
      }
      stack.push(i);
    }
    return ans;
  };
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) heights[c] = matrix[r]![c] === "1" ? heights[c]! + 1 : 0;
    best = Math.max(best, largestRectangle(heights));
  }
  return best;
}

Template connection

Monotonic stack histogram (LC84) on each row.

Deep dive

Treat each row as the base of a histogram: heights[c] = heights[c] + 1 if matrix[r][c] == '1', else reset to 0. After updating the histogram for row r, run largest rectangle in histogram (LC 84). The answer is the max over all rows. This reduces a 2D problem to rows calls of the 1D monotonic-stack template.

Reflection