#1074. Number of Submatrices That Sum to Target

ยท

1 min read

https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/description/?envType=daily-question&envId=2024-01-28

function numSubmatrixSumTarget(matrix, target) {
    const rows = matrix.length;
    const cols = matrix[0].length;
    let count = 0;

    // Compute prefix sum for each row
    const prefixSum = [];
    for (let row = 0; row < rows; row++) {
        prefixSum[row] = [];
        prefixSum[row][0] = matrix[row][0];
        for (let col = 1; col < cols; col++) {
            prefixSum[row][col] = prefixSum[row][col - 1] + matrix[row][col];
        }
    }

    for (let startCol = 0; startCol < cols; startCol++) {
        for (let endCol = startCol; endCol < cols; endCol++) {

            const seen = new Map();
            let curSum = 0;
            seen.set(0, 1); 

            for (let row = 0; row < rows; row++) {
                curSum += prefixSum[row][endCol] - (startCol > 0 ? prefixSum[row][startCol - 1] : 0);

                if (seen.has(curSum - target)) {
                    count += seen.get(curSum - target);
                }

                seen.set(curSum, (seen.get(curSum) || 0) + 1);
            }
        }
    }

    return count;
}

I don't understand this solution.

ย