Max Rectangle in Binary Matrix

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.

Bonus if you can solve it in O(n^2) or less.

A : [  1 1 1
       0 1 1
       1 0 0 
    ]

Output : 4 

As the max area rectangle is created by the 2x2 rectangle created by (0,1), (0,2), (1,1) and (1,2)

Method:

Build histogram first, and then find the largest rectangle in the histogram

Solution:

Time: O(n^2)
Space: O(n^2)

public class Solution {
    public int maximalRectangle(int[][] A) {
        // 1 1 1      1 1 1
        // 0 1 1  =>  0 2 2  
        // 1 0 0      1 0 0
        int m = A.length;
        if (m == 0) return 0;
        int n = A[0].length;
        if (n == 0) return 0;
        // add an extra column and fill with 0 to make later calculation easier
        int[][] hist = new int[m][n + 1];
        // build histogram
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                if (i == 0) {
                    hist[i][j] = A[i][j];
                } else if (A[i][j] == 1) {
                    hist[i][j] = hist[i - 1][j] + 1;
                }
            }
        }
        int max = 0;
        for (int i = 0; i < m; i ++) {
            Deque<Integer> stack = new ArrayDeque<>();
            for (int j = 0; j <= n; j ++) {
                // keep poping stack if curElement is smaller
                while (!stack.isEmpty() && hist[i][j] < hist[i][stack.peekFirst()]) {
                    int height = hist[i][stack.pop()];
                    int left = stack.isEmpty() ? 0 : stack.peekFirst() + 1;
                    int width = j - left;
                    max = Math.max(max, height * width);
                }
                stack.push(j);
            }
        }
        // for (int[] arr : hist) {
        //     System.out.println(Arrays.toString(arr));
        // }
        return max;
    }
}