Max rectangle

Given a binary matrix M of size n X m. Find the maximum area of a rectangle formed only of 1s in the given matrix.

• Time : O(nm)
• Space : O(m)

class Solution{
    int helper(vector<int> dp) {
        int res = 0, n = dp.size();
        vector<pair<int, int>> st;
        for(int i = 0; i < n; i++) {
            int left = i;
            while(!st.empty() and st.back().second >= dp[i]) {
                res = max(res, (i - st.back().first) * st.back().second);
                left = st.back().first;
                st.pop_back();
            }
            st.push_back({left, dp[i]});
        }
        for(int i = 0; i < st.size(); i++) {
            res = max(res, (n - st[i].first) * st[i].second);
        }
        return res;
    }
public:
    int maxArea(int M[MAX][MAX], int n, int m) {
        vector<int> dp(m);
        int res = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(M[i][j] == 0) dp[j] = 0;
                else dp[j] += 1;
            }
            res = max(res, helper(dp));
        }
        return res;
    }
};