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 Sam K., 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

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →