// 1. Brute force
// Time complexity : O(N^3M^3) 
// Space complexity : O(1)O(1).

//2. Stack based approach
//To compute the maximum area in our rectangle, we have to compute the maximum area of each histogram and find the global maximum. 
//this can be done by using a stack space that could store this histogram area

//Time complexity : O(NM)O(NM). Running leetcode84 on each row takes M (length of each row) time. This is done N times for O(NM)O(NM).
//Space complexity : O(M)O(M). We allocate an array the size of the the number of columns to store our widths at each row.

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;
    }