 All Problems
Largest Rectangle in Binary Matrix
hard
stack
arrays
dynamic programming
monotonic stack
amazon
google
microsoft
facebook

Given an m × n binary matrix filled with 0s and 1s, find the largest rectangle containing only 1s and return its area.

Example 1:

Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 6

Example 2:

Input:
0
Output: 0

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 ≤ m, n ≤ 200
  • matrix[i][j] is '0' or '1'

Input format: m lines, each with n space-separated integers (0 or 1).

Output format: Maximum rectangle area.

Run to check your code against the sample cases, or submit to run every case