Maximum Size Square Sub-matrix

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

int helper(vector<int> A) {
    int res = 0;
    A.push_back(0);
    vector<pair<int, int>> st;
    for(int i = 0; i < A.size(); i++) {
        int p = i;
        while(st.size() and st.back().second >= A[i]) {
            int h = st.back().second, w = (i - st.back().first);
            res = max(res, min(h,w) * min(h,w));
            p = st.back().first;
            st.pop_back();
        }
        st.push_back({p, A[i]});
    }
    
    return res;
}

int Solution::solve(vector<vector<int> > &A) {
    int n = A.size(), m = A[0].size(), res = 0;
    vector<int> dp(m);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(A[i][j]) dp[j] += 1;
            else dp[j] = 0;
        }
        res = max(res, helper(dp));
    }
    return res;
}