LeetCode Problem : Maximal Rectangle

Problem

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

Code

int largestRectangleArea(vector<int> &A) {
    int n = A.size();
    vector<int> left(n,0),right(n,0);
    int max_area = 0;
    right[n - 1] = n - 1;
    for(int i = 1;i < n; ++i){
        if(A[i] > A[i - 1])
            left[i] = i;
        else{
            int j = left[i - 1];
            while(j > 0 && A[i] <= A[j - 1])
                --j;
            left[i] = j;
        }
    }
    for(int i = n - 2;i >= 0; --i){
        if(A[i] > A[i + 1])
            right[i] = i;
        else{
            int j = right[i + 1];
            while(j < n - 1 && A[i] <= A[j + 1])
                ++j;
            right[i] = j;
        }
    }
    for(int i = 0;i < n; ++i){
        int area = A[i]*(right[i] - left[i] + 1);
        if(max_area < area)
            max_area = area;
    }
    return max_area;
}
int maximalRectangle(vector<vector<char> > &matrix) {
    // IMPORTANT: Please reset any member data you declared, as
    // the same Solution instance will be reused for each test case.
    int m = matrix.size();
    if(m == 0)
        return 0;
    int n = matrix[0].size();
    vector<vector<int> > h(m,vector<int>(n,0)); 
    for(int j = 0;j < n; ++j){
        if(matrix[m - 1][j] == '1')
        h[m - 1][j] = 1;
    }
    for(int j = 0;j < n; ++j){
        for(int i = m - 2;i >= 0; --i){
            if(matrix[i][j] == '1')
            h[i][j] = h[i + 1][j] + 1;
        }
    }
    int max_area = 0;
    for(int i = 0;i < m; ++i){
        int area = largestRectangleArea(h[i]);
        if(max_area < area)
            max_area = area;
    }
    return max_area;
}