Guru Level
Implement the maximalRectangleArea method that returns the largest rectangle of ones in a binary matrix.
You are given a binary matrix containing only 0 and 1. Return the area of the largest rectangle that contains only 1s.
The rectangle must be aligned with the rows and columns of the matrix.
Example 1
Input
matrix (int[][]) =
[[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]rows (int) =
4cols (int) =
5Returns (int)
6Example 2
Input
matrix (int[][]) =
[[0]]rows (int) =
1cols (int) =
1Returns (int)
0Example 3
Input
matrix (int[][]) =
[[1,1],[1,1]]rows (int) =
2cols (int) =
2Returns (int)
4Convert each row into a histogram problem.
Maintain an array of column heights. For every row, if a cell contains 1, increase that column height; otherwise reset it to zero. After updating heights for a row, calculate the largest rectangle in that histogram using a monotonic stack.
The maximum over all rows is the final answer.
Pseudocode:
function maximalRectangleArea(matrix, rows, cols):
heights = array of cols filled with 0
best = 0
for r from 0 to rows - 1:
for c from 0 to cols - 1:
if matrix[r][c] == 1:
heights[c]++
else:
heights[c] = 0
best = max(best, largestRectangleInHistogram(heights))
return bestReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run