Number of Submatrices That Sum to Target

#1

quesn - https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/
my code -https://ide.codingblocks.com/s/336743

#2

You need to optimize ur code. Think of the following way:

  1. Calculate the sum of submatix from (0,0) to current (i,j) by using : dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1].
  2. Now for each possible x and y calculate the sum of the rectangle having left - top element as x,y and right bottom element as (i,j) using dp[i][j] - dp[x-1][j] - dp[i][y-1] + dp[x-1][y-1] and check whether this is equal to target sum or not.
#3

okk i get that I can solve it using prefix sum but time complexity would be similar in both the cases

#4

I saw this solution on leetcode (similar to the code I sent earlier) but I’m unable to understand https://ide.codingblocks.com/s/337278why this is working