Watch 10 video solutions for Number of Submatrices That Sum to Target, a hard level problem involving Array, Hash Table, Matrix. This walkthrough by Algorithms Made Easy has 25,002 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a matrix and a target, return the number of non-empty submatrices that sum to target.
A submatrix x1, y1, x2, y2 is the set of all cells matrix[x][y] with x1 <= x <= x2 and y1 <= y <= y2.
Two submatrices (x1, y1, x2, y2) and (x1', y1', x2', y2') are different if they have some coordinate that is different: for example, if x1 != x1'.
Example 1:
Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0 Output: 4 Explanation: The four 1x1 submatrices that only contain 0.
Example 2:
Input: matrix = [[1,-1],[-1,1]], target = 0 Output: 5 Explanation: The two 1x2 submatrices, plus the two 2x1 submatrices, plus the 2x2 submatrix.
Example 3:
Input: matrix = [[904]], target = 0 Output: 0
Constraints:
1 <= matrix.length <= 1001 <= matrix[0].length <= 100-1000 <= matrix[i][j] <= 1000-10^8 <= target <= 10^8