Skip to main content

85. Maximal Rectangle

hard

Find the area of the largest rectangle of 1s in a binary matrix. The elegant reduction — treat each row as the base of a histogram — turns this into Largest Rectangle in Histogram m times.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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

Constraints

  • rows == matrix.length
  • cols == matrix[i].length
  • 1 <= row, cols <= 200
  • matrix[i][j] is '0' or '1'.

Examples

Example 1

Input
matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output
6

Explanation: The maximal rectangle is shown in the above picture.

Example 2

Input
matrix = [["0"]]
Output
0

Example 3

Input
matrix = [["1"]]
Output
1

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Imagine each row as the ground line of a histogram whose bar heights are the count of consecutive 1s above (and including) that cell.

Hint 2

If you can solve Largest Rectangle in Histogram in O(n), you can solve this in O(m * n) — one histogram sweep per row.

Hint 3

For row i, heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0. Track the rolling max across all rows.

Solution approach

Reveal approach

Reduce to Largest Rectangle in Histogram. Maintain a heights[] array of length cols. For each row, update heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0. Then compute the largest rectangle in that histogram using a monotonic stack: for each bar, find the nearest shorter bar to the left and right, the area for that bar is height * (right - left - 1). Track the global max across all rows. The monotonic-stack histogram subroutine runs in O(cols) per row, giving O(m * n) total. Alternative pure-DP: maintain left[j], right[j], height[j] arrays per row tracking the maximum-width window of 1s centered on (i, j); same complexity, more bookkeeping.

Complexity

Time
O(m * n)
Space
O(n)

Related patterns

  • dynamic-programming
  • monotonic-stack
  • grid-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Maximal Rectangle and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →