Array Matrix Breadth First Search
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) = 4
cols (int) = 5
Return:
(int) 6
Example 2
Input:
matrix (int[][]) = [[0]]
rows (int) = 1
cols (int) = 1
Return:
(int) 0
Example 3
Input:
matrix (int[][]) = [[1,1],[1,1]]
rows (int) = 2
cols (int) = 2
Return:
(int) 4

Convert 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 best
Run your code to see the result.