Maximal Rectangle

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

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

Analysis

It's not a easy problem, yet if you've done "Largest Rectangle in Histogram", one approach is convert to that problem for each row, and get "largest rectangle in histogram" for each row, and compare each row's "largest rectangle" to get maximal rectangle in the matrix.

For example:

Original matrix[][]

[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]

convert to =>

heights[][] matrix

[
  [1, 0, 1, 0, 0],
  [2, 0, 2, 1, 1],
  [3, 1, 3, 2, 2],
  [4, 0, 0, 3, 0]
]

That for heights[i][j] it stands for, for i-th row, the height at column j, thus each row in heights[i][j] could just be input for the function int largestRectangleArea(int[] heights).

At this moment, the "Maximal Rectangle" problem has been converted to a series of "Largest Rectangle in Histogram" problem.

O(n\*m) time, O(n\*m) space

Solution

Convert to Largest Rectangle in Histogram problem (where DP is used) - 13 ms, faster than 70.66%

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int rowLength = matrix.length;
        int colLength = matrix[0].length;
        int[][] heights = new int[rowLength][colLength];
        for (int i = 0 ; i < rowLength; i++) {
            for (int j = 0; j < colLength; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0) heights[i][j] = 1;
                    if (i > 0) heights[i][j] = heights[i-1][j] + 1;
                } else {
                    heights[i][j] = 0;
                }
            }
        }
        int max = 0;
        for (int[] hs : heights) {
            max = Math.max(max, largestRectangleArea(hs));
        }
        return max;
    }

    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        if (heights.length == 1) {
            return heights[0];
        }
        int maxArea = 0;
        int[] leftBound = new int[heights.length];
        int[] rightBound = new int[heights.length];
        leftBound[0] = -1;
        rightBound[heights.length - 1] = heights.length;

        for (int i = 1; i < heights.length; i++) {
            int l = i - 1;
            while (l >= 0 && heights[l] >= heights[i]) {
                l = leftBound[l];
            }
            leftBound[i] = l;
        }
        for (int i = heights.length - 2; i >= 0; i--) {
            int r = i + 1;
            while (r < heights.length && heights[r] >= heights[i]) {
                r = rightBound[r];
            }
            rightBound[i] = r;
        }

        for (int i = 0; i< heights.length; i++) {
            maxArea = Math.max(heights[i] * (rightBound[i] - leftBound[i] - 1), maxArea);
        }
        return maxArea;
    } 
}

Convert to largest rectangle histogram (where monotonous stack is used) - (35 ms AC)

class Solution {

    // O(n*m)
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length==0) return 0;
        int[] heights = new int[matrix[0].length];
        int maxArea=-1;
        for(int i=0; i<matrix.length; i++){
            for(int j=0; j<matrix[0].length; j++){
                // if (matrix[i][j] == '0') heights[j] = 0;
                // else heights[j]++;
                if (matrix[i][j] == '1') heights[j]++;
                else heights[j] = 0;
            }            
            int area = largestRectangleArea(heights);
            maxArea = Math.max(maxArea, area);
        }
        return maxArea;
    }

    // O(n)
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int maxarea = 0;
        for (int i = 0; i < heights.length; i++) {
            while (stack.peek() != -1 && heights[stack.peek()] >= heights[i])
                maxarea = Math.max(maxarea, heights[stack.pop()] * (i - stack.peek() - 1));
            stack.push(i);
        }
        while (stack.peek() != -1)
            maxarea = Math.max(maxarea, heights[stack.pop()] * (heights.length - stack.peek() -1));
        return maxarea;
    }
}

Combining largestRectangleArea function into the same loop - using stack

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix==null||matrix.length==0||matrix[0].length==0)
            return 0;
        int cLen = matrix[0].length;    // column length
        int rLen = matrix.length;       // row length
        // height array 
        int[] h = new int[cLen+1];
        h[cLen]=0;
        int max = 0;


        for (int row=0;row<rLen;row++) {
            Stack<Integer> s = new Stack<Integer>();
            for (int i=0;i< cLen+1;i++) {
                if (i<cLen)
                    if(matrix[row][i]=='1')
                        h[i]+=1;
                    else h[i]=0;

                if (s.isEmpty()||h[s.peek()]<=h[i])
                    s.push(i);
                else {
                    while(!s.isEmpty()&&h[i]<h[s.peek()]){
                        int top = s.pop();
                        int area = h[top]*(s.isEmpty()?i:(i-s.peek()-1));
                        if (area>max)
                            max = area;
                    }
                    s.push(i);
                }
            }
        }
        return max;
    }
}

Another combined implementation - using Stack - (35 ms, faster than 37.38% )

class Solution {
    public int maximalRectangle(char[][] matrix) {
       int rLen = matrix.length, cLen = rLen == 0 ? 0 : matrix[0].length, max = 0;
        int[] h = new int[cLen+1];

        for (int row = 0; row < rLen; row++) {
            Stack<Integer> s = new Stack<Integer>();
            s.push(-1);
            for (int i = 0; i <= cLen ;i++) {
                if(i < cLen && matrix[row][i] == '1')
                    h[i] += 1;
                else h[i] = 0;

                while(s.peek() != -1 && h[i] < h[s.peek()]) {
                    max = Math.max(max, h[s.pop()] * (i - s.peek() - 1));
                }
                s.push(i);
            }
        }
        return max;
    }
}

Reference

• LeetCode: O(n^2) solution based on largest rectangle in histogram