LeetCode Maximal Rectangle: O(m * n) Solution and DP

Overview

LeetCode Maximal Rectangle: 1) Dynamic Programming with O(m * n * m) time; 2) Use Largest Rectangle in Histogram (Increasing Stack) to get O(m * n) approach.

LeetCode Maximal Rectangle

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

Solution and Precautions: O(m * n) Solution and DP

(1) brute force: enumerate all the sub matrix (O(N^2)) where N = m * n, check each submatrix contains all ones or not. If so, update the maximal area if possible, this takes another O(N) time. So it is O(N^3) where N  = m * n

(2) Dynamic Programming (DP): let dp[i][j] denote the consecutive 1′s in row i from point (i, j) until the last consecutive 1 to the right. It takes O(m * n) to get all values.

then we take each point (i, j) as the top left corner of the rectangle and to get the maximal rectangle with (i, j) being the left top corner. This could be achieved by scanning from row i until the last row or until the width of the rectangle becomes 0. It takes O(m) to get it. So this takes O(m * n * m) time.

The following Java code implements this idea and is accepted by the LeetCode OJ to pass this Maximal Rectangle problem:

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if (m < 1)
            return 0;
        int n = matrix[0].length;

        int [][] dp = new int[m][n];
        for (int i = 0; i < m; ++i) {
            dp[i][n-1] = ('0' == matrix[i][n-1]) ? 0 : 1;
            for (int j = n - 2; j >= 0; --j) {
                dp[i][j] = ('0' == matrix[i][j]) ? 0 : 1 + dp[i][j+1]; // DP!
            }
        }

        int maxArea = 0;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j) {
                int width = dp[i][j];
                for (int k = i; k < m && width > 0; ++k) {
                    width = Math.min(width, dp[k][j]);
                    maxArea = Math.max(maxArea, (k - i + 1) * width);
                }
            }
        return maxArea;

    }
}

(3) O(m * n) solution. Remember the “leetcode: Largest Rectangle in Histogram” problem. We then treat each row as the x coordinate  and it takes O(m * n) to get all the heights for each row, by adopting the same linear approach to get maximal rectangle for each row, we achieve to get the global maximal rectangle in O(m * n) time. The following Java code implements this idea and is accepted by the LeetCode OJ to pass this Maximal Rectangle problem:

public class Solution {
    private int largestRectangle(int[] height) {
        int n = height.length;

        Stack<Integer> stk = new Stack<Integer>();
        int maxRect = 0;
        for (int i = 0; i < n; ++i) {
            if (stk.empty() || height[i] >= height[stk.peek()])
                stk.push(i);
            else {
                int mid  = stk.pop();
                int left = stk.empty() ? -1 : stk.peek();
                maxRect  = Math.max(maxRect, height[mid] * (i - left - 1));
                --i;
            }
        }

        while (!stk.empty()) {
            int mid  = stk.pop();
            int left = stk.empty() ? -1 : stk.peek();
            maxRect  = Math.max(maxRect, height[mid] * (n - left - 1));
        }

        return maxRect;
    }

    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if (m < 1)
            return 0;
        int n = matrix[0].length;

        int [][] height = new int[m][n];

        for (int j = 0; j < n; ++j) {
            height[m-1][j] = ('0' == matrix[m-1][j]) ? 0 : 1;
            for (int i = m - 2; i >= 0; --i) {
                height[i][j] = ('0' == matrix[i][j]) ? 0 : 1 + height[i+1][j];
            }
        }

        int maxArea = 0;
        for (int i = 0; i < m; ++i)
            maxArea = Math.max(maxArea, largestRectangle(height[i]));
        return maxArea;
    }
}

Summary

LeetCode Maximal Rectangle: 1) Dynamic Programming with O(m * n * m) time; 2) Use Largest Rectangle in Histogram (Increasing Stack) to get O(m * n) approach.

Written on June 15, 2013