1074. Number of Submatrices that Sum to Target - Explanation

1. Brute Force

class Solution:
    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
        ROWS, COLS = len(matrix), len(matrix[0])
        res = 0

        for r1 in range(ROWS):
            for r2 in range(r1, ROWS):
                for c1 in range(COLS):
                    for c2 in range(c1, COLS):
                        subSum = 0
                        for r in range(r1, r2 + 1):
                            for c in range(c1, c2 + 1):
                                subSum += matrix[r][c]

                        if subSum == target:
                            res += 1

        return res

Time & Space Complexity

Time complexity: $O(m ^ 3 * n ^ 3)$
Space complexity: $O(1)$ extra space.

Where $m$ is the number of rows and $n$ is the number of columns of the given matrix.

2. Two Dimensional Prefix Sum

class Solution:
    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
        ROWS, COLS = len(matrix), len(matrix[0])
        sub_sum = [[0] * COLS for _ in range(ROWS)]

        for r in range(ROWS):
            for c in range(COLS):
                top = sub_sum[r - 1][c] if r > 0 else 0
                left = sub_sum[r][c - 1] if c > 0 else 0
                top_left = sub_sum[r - 1][c - 1] if min(r, c) > 0 else 0
                sub_sum[r][c] = matrix[r][c] + top + left - top_left

        res = 0
        for r1 in range(ROWS):
            for r2 in range(r1, ROWS):
                for c1 in range(COLS):
                    for c2 in range(c1, COLS):
                        top = sub_sum[r1 - 1][c2] if r1 > 0 else 0
                        left = sub_sum[r2][c1 - 1] if c1 > 0 else 0
                        top_left = sub_sum[r1 - 1][c1 - 1] if min(r1, c1) > 0 else 0
                        cur_sum = sub_sum[r2][c2] - top - left + top_left
                        if cur_sum == target:
                            res += 1
        return res

Time & Space Complexity

Time complexity: $O(m ^ 2 * n ^ 2)$
Space complexity: $O(m * n)$

Where $m$ is the number of rows and $n$ is the number of columns of the given matrix.

3. Horizontal 1D Prefix Sum

class Solution:
    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
        ROWS, COLS = len(matrix), len(matrix[0])
        sub_sum = [[0] * COLS for _ in range(ROWS)]

        for r in range(ROWS):
            for c in range(COLS):
                top = sub_sum[r - 1][c] if r > 0 else 0
                left = sub_sum[r][c - 1] if c > 0 else 0
                top_left = sub_sum[r - 1][c - 1] if min(r, c) > 0 else 0
                sub_sum[r][c] = matrix[r][c] + top + left - top_left

        res = 0
        for r1 in range(ROWS):
            for r2 in range(r1, ROWS):
                count = defaultdict(int)
                count[0] = 1
                for c in range(COLS):
                    cur_sum = sub_sum[r2][c] - (sub_sum[r1 - 1][c] if r1 > 0 else 0)
                    res += count[cur_sum - target]
                    count[cur_sum] += 1

        return res

Time & Space Complexity

Time complexity: $O(m ^ 2 * n)$
Space complexity: $O(m * n)$

Where $m$ is the number of rows and $n$ is the number of columns of the given matrix.

4. Vertical 1D Prefix Sum

class Solution:
    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
        ROWS, COLS = len(matrix), len(matrix[0])
        res = 0

        for c1 in range(COLS):
            row_prefix = [0] * ROWS
            for c2 in range(c1, COLS):
                for r in range(ROWS):
                    row_prefix[r] += matrix[r][c2]

                count = defaultdict(int)
                count[0] = 1
                cur_sum = 0
                for r in range(ROWS):
                    cur_sum += row_prefix[r]
                    res += count[cur_sum - target]
                    count[cur_sum] += 1

        return res

Time & Space Complexity

Time complexity: $O(m * n ^ 2)$
Space complexity: $O(m)$

Where $m$ is the number of rows and $n$ is the number of columns of the given matrix.