@@ -0,0 +1,2603 @@
+/***%0A * Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.%0A */%0Apublic class Solution %7B%0A    // Brute force idea O(m(m-1)/2 * n (n-1)/2)%0A    %0A    // Solution 1: O(n%5E3)%0A    /*%0A    public int maximalRectangle(char%5B%5D%5B%5D matrix) %7B%0A        int area = 0;%0A        int numRows = matrix.length;%0A        if (numRows == 0)   return 0;%0A        int numCols = matrix%5B0%5D.length;%0A        int rowArea%5B%5D%5B%5D = new int %5BnumRows%5D%5BnumCols%5D;%0A        for (int i = 0; i %3C numRows; i++)%0A            for (int j = 0; j %3C numCols; j++) %7B%0A                // calculate max area bottom left start at (i, j)%0A                if (matrix%5Bi%5D%5Bj%5D == '0') continue;%0A                // update height matrix%0A                if (j == 0) rowArea%5Bi%5D%5Bj%5D = 1;%0A                else %0A                    rowArea%5Bi%5D%5Bj%5D = rowArea%5Bi%5D%5Bj - 1%5D + 1;%0A                int y = 1;%0A                int x = numCols;%0A                while (i - y + 1 %3E= 0 && rowArea%5Bi - y + 1%5D%5Bj%5D %3E 0) %7B%0A                    x = Math.min(x, rowArea%5Bi - y + 1%5D%5Bj%5D);%0A                    area = Math.max(area, x*y);%0A                    y++;%0A                %7D%0A                //%0A            %7D%0A        return area;%0A    %7D%0A    */%0A    %0A    // Solution 2: O(n%5E2), O(n)%0A    // Idea: Maintain a Left, Right, and Height array during area%0A    // calculation. %0A    // For each Row:%0A    //  First update Left and Height array, If meet '0', turn left to 0, right to n, and height to n, and increase left.%0A    //  Then update Right array and Area. If meet '0', set right to j.%0A    public int maximalRectangle(char%5B%5D%5B%5D matrix) %7B%0A        int m = matrix.length;%0A        if (m == 0) return 0;%0A        int n = matrix%5B0%5D.length;%0A        int H%5B%5D = new int%5Bn%5D;%0A        int L%5B%5D = new int%5Bn%5D;%0A        int R%5B%5D = new int%5Bn%5D;%0A        // L, R are both used for scanning and calculation purpose.%0A        Arrays.fill(R, n);%0A%0A        int ret = 0;%0A        for (int i = 0; i %3C m; i++) %7B%0A            int left = 0, right = n;%0A            for (int j = 0; j %3C n; j++) %7B%0A                if (matrix%5Bi%5D%5Bj%5D == '1') %7B%0A                    ++H%5Bj%5D;%0A                    L%5Bj%5D = Math.max(L%5Bj%5D, left);%0A                %7D else %7B%0A                    left = j + 1;%0A                    H%5Bj%5D = 0; L%5Bj%5D = 0; R%5Bj%5D = n;%0A                %7D%0A            %7D%0A%0A            for (int j = n - 1; j %3E= 0; j--) %7B%0A                if (matrix%5Bi%5D%5Bj%5D == '1') %7B%0A                    R%5Bj%5D = Math.min(R%5Bj%5D, right);%0A                    ret = Math.max(ret, H%5Bj%5D * (R%5Bj%5D - L%5Bj%5D));%0A                %7D else %7B%0A                    right = j;%0A                %7D%0A            %7D%0A        %7D%0A        return ret;%0A    %7D%0A%7D%0A

add MaximalRectangle.java