Number of Submatrices That Sum to Target

lcpy gen -n 1074   # by problem number
lcpy gen -s number_of_submatrices_that_sum_to_target   # by problem name

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.

Input: matrix = [[1,-1],[-1,1]], target = 0
Output: 5
Explanation: The two 1x2 submatrices, plus the two 2x1 submatrices, plus the 2x2 submatrix.

Input: matrix = [[904]], target = 0
Output: 0

class Solution:
    # Time: O(rows^2 * cols)
    # Space: O(cols)
    def num_submatrix_sum_target(self, matrix: list[list[int]], target: int) -> int:
        rows, cols = len(matrix), len(matrix[0])
        count = 0
        for top in range(rows):
            col_sums = [0] * cols
            for bottom in range(top, rows):
                for c in range(cols):
                    col_sums[c] += matrix[bottom][c]
                prefix: dict[int, int] = {0: 1}
                running = 0
                for s in col_sums:
                    running += s
                    count += prefix.get(running - target, 0)
                    prefix[running] = prefix.get(running, 0) + 1
        return count