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

&nbsp;
Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.


Example 2:

Input: matrix = [["0"]]
Output: 0


Example 3:

Input: matrix = [["1"]]
Output: 1


&nbsp;
Constraints:


	rows == matrix.length
	cols == matrix[i].length
	1 &lt;= row, cols &lt;= 200
	matrix[i][j] is '0' or '1'.


class Solution:
    def maxArea(self,arr: List[List[int]]) -> int:
        maxA = 0 #local max variable to return max area of a 1D array
        stack = [-1] #initializing with minimum value so we can avoid using loop for remaining element in the stack after whole traversing
        arr.append(-1) # value for stack index -1 and one extra iteration to empty the stack
        for i in range(len(arr)): # traversing for stack from left to right
            arr[i] = int(arr[i]) # we are getting str value from matrix
            while stack and arr[stack[-1]] >= int(arr[i]): #stack is non empty and stack top is greater or equal to current element
                index = stack.pop() #pop greater element from stack and finds its area
                width = i - stack[-1] - 1 if stack else i # for empty stack width is len of 1D arr, and after poping if we have element in stack then it becomes left boundary and current index as right boundary
                maxA = max(maxA, width * arr[index]) # geting max area (L * B)
            stack.append(int(i)) # inserting each element in stack
        return maxA # return the max area
    """Below is the code for adding each row one by one and passing it to above function to get the max area for each row"""
    # r1 - 1 0 1 0 0
    # r2 - 1 0 1 1 1
    # r = 2 0 2 1 1 This is for else condition

    # r1 - 1 1 1 0 1
    # r2 - 1 0 1 1 0
    # r = 2 0 2 1 0 This is for if condition

    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        result = [0] * len(matrix[0])
        maxReact = 0
        maxReact = self.maxArea(result)
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                matrix[i][j] = int(matrix[i][j])
                if matrix[i][j] == 0:
                    result[j] = 0
                else:
                    result[j] = result[j] + matrix[i][j]
            maxReact = max(maxReact,self.maxArea(result)) #after getting max area for 1D arr we are getting max value from those 1D arr for the 2D arr
        return maxReact
class Solution {
    public int maximalRectangle(char[][] matrix) {
        ArrayList<Integer> list = new ArrayList<>();
        int n = matrix[0].length;
        for(int i=0; i<n; i++){
            list.add(Character.getNumericValue(matrix[0][i]));
        }

        int maxArea = maximumArea(list);
        int m = matrix.length;

        for(int i=1; i<m; i++){
            for(int j=0; j<n; j++){
                if(matrix[i][j] == '1'){
                    list.set(j, Character.getNumericValue(matrix[i][j]) + list.get(j));
                }else
                    list.set(j, 0);
            }
            maxArea = Math.max(maxArea, maximumArea(list));
        }
        return maxArea;
    }
    public int maximumArea(ArrayList<Integer> heights) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        int n = heights.size();
        int[] left = new int[n];
        int[] right = new int[n];
        int[] width = new int[n];

        for(int i=0; i<n; i++){
            while(!stack1.isEmpty() && heights.get(stack1.peek()) >= heights.get(i))
                stack1.pop();
            if(!stack1.isEmpty())
                left[i] = stack1.peek();
            else
                left[i] = -1;
            stack1.push(i);
        }

        for(int i=n-1; i>=0; i--){
            while(!stack2.isEmpty() && heights.get(stack2.peek()) >= heights.get(i))
                stack2.pop();
            if(!stack2.isEmpty())
                right[i] = stack2.peek();
            else
                right[i] = n;
            stack2.push(i);
        }

        for(int i=0; i<n; i++){
            width[i] = right[i] - left[i] - 1;
        }
        int mxArea = 0;
        for(int i=0; i<n; i++){
            mxArea = Math.max(mxArea, width[i] * heights.get(i));
        }
        return mxArea;
    }
}
class Solution {
private:
    vector<int> nextSmallerElement(int *arr , int n){
        stack<int> st;
        st.push(-1);
        vector<int> ans(n);
        
        for(int i = n - 1 ; i >= 0 ; i--){
            int curr = arr[i];
            
            while(st.top() != -1 && arr[st.top()] >= curr){
                st.pop();
            }
            
            ans[i] = st.top();
            st.push(i);
        }
        return ans;
    }
    
    vector<int> prevSmallerElement(int *arr , int n){
        stack<int> st;
        st.push(-1);
        vector<int> ans(n);
        
        for(int i = 0; i < n ; i++){
            int curr = arr[i];
            
            while(st.top() != -1 && arr[st.top()] >= curr){
                st.pop();
            }
            
            ans[i] = st.top();
            st.push(i);
        }
        return ans;
    }
    
    int largestRectangleArea(int * heights , int n){
        int area = INT_MIN;
        
        vector<int> next(n);
        next = nextSmallerElement(heights , n);
        
        vector<int> prev(n);
        prev = prevSmallerElement(heights , n);
        
        for(int i = 0 ; i < n ; i++){
            int length = heights[i];
            
            if(next[i] == -1)
                next[i] = n;
            
            int breadth = next[i] - prev[i] - 1;
            int newArea = length * breadth;
            area = max(area , newArea);
        }
        return area;
    }
    
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        
        int n = matrix.size();
        int m = matrix[0].size();
        int M[n][m];
        
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                M[i][j] = matrix[i][j] - '0';
            }
        }
                
        //step 1 : compute area of 1st row
        int area = largestRectangleArea(M[0] , m);
        
        for(int i = 1 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                
        //step 2 : add upar wala element if it is 1
                if(M[i][j] != 0)
                    M[i][j] = M[i][j] + M[i-1][j];
                    
                else
                    M[i][j] = 0;
            }
            
            area = max(area , largestRectangleArea(M[i] , m));
        }
        return area;
    }
};
var maximalRectangle = function(matrix) {
    const m = matrix.length;
    const n = matrix[m - 1].length;

    const prefixSum = new Array(m).fill().map(() => new Array(n).fill(0));
    for(let i = 0; i < m; i += 1) {
        for(let j = 0; j < n; j += 1) {
            prefixSum[i][j] = parseInt(matrix[i][j]);
            if(i > 0 && prefixSum[i][j] > 0) {
                prefixSum[i][j] += prefixSum[i - 1][j];
            }
        }
    }

    const getArea = (currentRow) => {
        let max = 0;
        for(let i = 0; i < n; i += 1) {
            const height = currentRow[i];

            let leftBoundary = i;
            while(leftBoundary >= 0 && currentRow[leftBoundary] >= currentRow[i]) {
                leftBoundary -= 1;
            }

            let rightBoundary = i;
            while(rightBoundary < n && currentRow[rightBoundary] >= currentRow[i]) {
                rightBoundary += 1;
            }

            const width = rightBoundary - leftBoundary - 1;
            max = Math.max(max, height * width);
        }

        return max;
    }

    let max = 0;
    for(let i = 0; i < m; i += 1) {
        max = Math.max(max, getArea(prefixSum[i]));
    }

    return max;
};
Maximal Rectangle