PreviousNext
Coding/Arrays and strings

Submatrix sum count

Write codeMedium25 minGoogle style

Your task

Given an m x n integer matrix and an integer target, count the number of (non-empty) axis-aligned submatrices whose elements sum exactly to target. A submatrix is defined by a contiguous range of rows and a contiguous range of columns. Matrix dimensions are up to 100 x 100 and entries may be negative.

Examples

count_target_submatrices(matrix: list[list[int]], target: int) -> int
Example 1
Inputcount_target_submatrices([[0, 1, 0], [1, 1, 1], [0, 1, 0]], 0)
Output4