1292. Maximum Side Length of a Square with... Accepted

class Solution {
public:
    vector<vector<int>> get_prefix_sum(const vector<vector<int>>& mat)
    {
        vector<vector<int>> prefix_sum(mat.size(), vector<int>(mat[0].size()));
        for (int i = 0; i < mat.size(); i++)
        {
            for (int j = 0; j < mat[i].size(); j++)
            {
                int left = j - 1 >= 0 ? prefix_sum[i][j - 1] : 0;
                int top = i - 1 >= 0 ? prefix_sum[i - 1][j] : 0;
                int left_top = j - 1 >= 0 && i - 1 >= 0 ? prefix_sum[i - 1][j - 1] : 0;

                prefix_sum[i][j] = left + top - left_top + mat[i][j];
            }
        }
        return prefix_sum;
    }

    int get_side_sum(
        int side_max,
        const vector<vector<int>>& prefix_sum,
        const vector<vector<int>>& mat
    )
    {
        int current_min = numeric_limits<int>::max();
        for (int i = 0; i < mat.size(); i++)
        {
            for (int j = 0; j < mat[i].size(); j++)
            {
                current_min = min(
                    current_min,
                    get_square_sum(prefix_sum, i, j, i + side_max - 1, j + side_max - 1)
                );
            }
        }

        return current_min;
    }

    int get_square_sum(
        const vector<vector<int>>& prefix_sum,
        int row1, int col1, int row2, int col2
    )
    {
        if (row2 >= prefix_sum.size() || col2 >= prefix_sum[0].size())
            return numeric_limits<int>::max();

        int A = prefix_sum[row2][col2];
        int B = col1 - 1 >= 0 ? prefix_sum[row2][col1 - 1] : 0;
        int C = row1 - 1 >= 0 ? prefix_sum[row1 - 1][col2] : 0;
        int D = row1 - 1 >= 0 && col1 - 1 >= 0 ? prefix_sum[row1-1][col1-1] : 0;

        int res = A - B - C + D;
        return res;
    }

    int maxSideLength(vector<vector<int>>& mat, int threshold) {
        if (mat.size() == 0)
            return 0;

        auto prefix_sum = get_prefix_sum(mat);

        int l = 0;
        int r = max(mat.size(), mat[0].size()) + 1;

        while (r - l > 1)
        {
            int m = l + (r - l) / 2;
            int sum = get_side_sum(m, prefix_sum, mat);
            if (sum <= threshold)
                l = m;
            else
                r = m;
        }

        return l;
    }
};