Heap overflow in Leetcode 1314

Question

Question : https://leetcode.com/problems/matrix-block-sum/

I am trying to solve it using 2D prefix sum where sum[i][j] is the sum of all the elements to its left side including the element and it's row and column.

Code :

class Solution {
public:
    int n, m;
    int getSum(int i, int j, vector<vector<int>>& sum) {
        if(i<0 || j<0) return 0;
        if (i >= n) i = m - 1;
        if (j >= n) j = m - 1;
        return sum[i][j];
    }
    
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        n = mat.size();
        m = mat[0].size();
        vector<vector<int>> sum(n, vector<int>(m, 0)), res(n, vector<int>(m, 0));
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                sum[i][j] = mat[i][j] + getSum(i-1, j, sum) + getSum(i, j-1, sum) - getSum(i-1, j-1, sum);
            }
        }
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                res[i][j] = getSum(i+k, j+k, sum) - getSum(i-k-1, j+k, sum) - getSum(i+k, j-k-1, sum) + getSum(i-k-1, j-k-1, sum);
            }
        }
        return res;
    }
};

Answer 1

• The bug would probably be in the last loop among those indices.

                res[i][j] = getSum(i+k, j+k, sum) - getSum(i-k-1, j+k, sum) - getSum(i+k, j-k-1, sum) + getSum(i-k-1, j-k-1, sum);

• Here is the same method with different variable names, would pass:

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <vector>

static const struct Solution {
        static const std::vector<std::vector<int>> matrixBlockSum(
                    const std::vector<std::vector<int>>& mat,
                    const int K
        ) {
            const std::size_t row_len = std::size(mat);
            const std::size_t col_len = row_len ? std::size(mat[0]) : 0;

            std::vector<std::vector<int>> sums(row_len, std::vector<int>(col_len, 0));

            for (std::size_t row = 0; row < row_len; ++row) {
                for (std::size_t col = 0; col < col_len; ++col) {
                    sums[row][col] = mat[row][col] +
                                     getPrefixSum(row - 1, col, sums) +
                                     getPrefixSum(row, col - 1, sums) -
                                     getPrefixSum(row - 1, col - 1, sums);
                }
            }

            std::vector<std::vector<int>> res(row_len, std::vector<int>(col_len, 0));

            for (std::size_t row = 0; row < row_len; ++row) {
                for (std::size_t col = 0; col < col_len; ++col) {
                    res[row][col] = getPrefixSum(row + K, col + K, sums) -
                                    getPrefixSum(row + K, col - K - 1, sums) -
                                    getPrefixSum(row - K - 1, col + K, sums) +
                                    getPrefixSum(row - K - 1, col - K - 1, sums);
                }
            }

            return res;
        }

    private:

        static const int getPrefixSum(
            int row,
            int col,
            const std::vector<std::vector<int>>& sums
        ) {
            if (row < 0 || col < 0) {
                return 0;
            }

            if (row >= std::size(sums)) {
                row = std::size(sums) - 1;
            }

            if (col >= std::size(sums[0])) {
                col = std::size(sums[0]) - 1;
            }

            return sums[row][col];
        }
};