Leetcode: Maximal Rectangle

This question is asked at Google, Bloomberg, and Apple. 

Given a rows x cols binary matrix filled with 0's and 1's find the largest rectangle containing only 1's and return its area. 

For example this matrix has input of [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] and the output of 6. 

Trivially we can enumerate every possible rectangle with all possible locations of coordinates (x1, y1) (x2, y2) and define a rectangle with the coordinates being opposite corners showing all of them contain 1's. Iterating over all possible coordinates is O(N^2 M^2) and iterating over a rectangle is O(NM). O(N^3 M^3) which is WAYYY too complex for practical terms and will not work for this problem. 

Another method to use is dynamic programming, first calculating the maximum width of a rectangle that ends up at a given coordinate in constant time. The maximal width is the running minimum width of each maximal width that is encountered inside the problem. 

Here are the definitions: 

maxWidth = min(maxWidth, widthHere)

curArea = maxWidth * (currentRow - originalRow + 1)

maxArea = max(maxArea, curArea)

For this question, we compute the maximum area for each histogram.

class Solution {

    public int maximalRectangle(char[][] matrix) {

        if(matrix.length == 0) return 0;

        int maxarea = 0;

        int[][] dp = new int[matrix.length][matrix[0].length];

        for(int i = 0; i < matrix.length; i++) {

            for(int j = 0; j < matrix[0].length; j++) {

                if(matrix[i][j] == '1') {

                    if(j == 0) {

                        dp[i][j] = 1;

                    } else {

                        dp[i][j] = dp[i][j - 1] + 1;

                    }

                    int width = dp[i][j];

                    for(int k = i; k >= 0; k--) {    

                        width = Math.min(width, dp[k][j]);

                        maxArea = Math.max(maxarea, width * (i - k + 1));

                    }

                }

            }

        }

        return maxArea;

    }

}

Now we have cubic time complexity, an improvement from the sixth exponential time complexity. So, a good thing to always do before you panic is to try to find the local maximum rectangle. 

We can convert the matrix into histograms and compute the maximal area of the rectangle in each of the histograms. This is very similar to the largest rectangle of a histogram.

How would we find the largest histogram in a matrix? We take elements row-wise. We sum the values that are in the rectangles. Here is an illustration.

We now calculate the maximum area of all of the histograms, respectively. We want to find the largest rectangular area of a histogram.

class Solution {

    // Get the maximum area in a histogram given its heights

    public int leetcode84(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;

    }

    public int maximalRectangle(char[][] matrix) {

        if (matrix.length == 0) return 0;

        int maxarea = 0;

        int[] dp = new int[matrix[0].length];

        for(int i = 0; i < matrix.length; i++) {

            for(int j = 0; j < matrix[0].length; j++) {

                // update the state of this row's histogram using the last row's histogram

                // by keeping track of the number of consecutive ones

                dp[j] = matrix[i][j] == '1' ? dp[j] + 1 : 0;

            }

            // update maxarea with the maximum area from this row's histogram

            maxarea = Math.max(maxarea, leetcode84(dp));

        } return maxarea;

    }

}

To make sense of this, I will be attempting the largest rectangle in histogram problem.