Maximal Rectangle -- Leetcode -- FB

Question:

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

Answer:

 /* Example: output: 6!

    0,0,0,1,0

    0,1,1,1,0

    1,0,1,1,0

    0,0,1,1,0

    0,0,0,0,1

    */

public class Solution {

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

        if(matrix==null)return 0;

        int m = matrix.length;

        if(m==0)return 0;

        if(matrix[0]==null)return 0;

        int n = matrix[0].length;

        

        int maxRecArea = 0;

        int[] dp = new int[n];

        

        //Time: O(m * n)

        for(int i=0; i<m; ++i){

            //Time: O(n)

            for(int j=0; j<n; ++j){

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

                    dp[j] += 1;

                }else{

                    dp[j] = 0;

                }

            }

            //Time: O(2 * n), Space: O(n)

            int area = largestRectangleArea(dp);

            maxRecArea = Math.max(maxRecArea, area);

        }

        return maxRecArea;

    }

//Time: O(n), Space: O(n)

    public int largestRectangleArea(int[] heights) {

        Stack<Integer> stack = new Stack<Integer>();

        int maxArea = 0;

        

        int[] h = new int[heights.length + 1];

        h = Arrays.copyOf(heights, heights.length + 1);

        

        int i=0;

        while(i < h.length){

            if(stack.isEmpty() || h[i] >= h[stack.peek()]){

                stack.push(i++);

            }else{

                //!stack.isEmpty() && h[i] < h[stack.peek()]

                int t = stack.pop();

                int area = 0;

                if(stack.isEmpty()){

                    area = h[t] * i;

                }else{

                    area = h[t] * (i - stack.peek() - 1);

                }

                maxArea = Math.max(maxArea, area);

            }

        }

        return maxArea;

    }

}