C++ | Prefix Sum | Subarray Sum based Explanation
The problem can be reduced to finding subarray sum in a 1D array with target value. We can find the 1D subarray sum for each combination of rows and then each s
The problem can be reduced to finding subarray sum in a 1D array with target value. We can find the 1D subarray sum for each combination of rows and then each subarray sum takes O(n) which makes the total time complexity O(n^3) since there will be n^2 combinations of rows.\n\nFirst we calculate the row prefix sum for the matrix so that each time we need to find the elements of rows r1 to r2 we can get it in O(n) since we won\'t need to sum all the elements in the row range again. And the sum of that row range can be calculated as sum[r2] - sum[r1-1]. \nFor Example1 the row prefix sum matrix would be: \n```\n0 1 0                                          0 1 0\n1 1 1                 =>                       1 2 1\n0 1 0                                          1 3 1\n\nRange [1,2] would sum to: [1 3 1]-[0 1 0] = [1 2 1] in the original matrix.\n```\nAnd then we can find the subarray sum equal to target in the above formed 1D array in linear time. For this refer [@560](https://leetcode.com/problems/subarray-sum-equals-k). And in the above 1D array any subarray sum from index l,r would correspond to sum of submatrix having upper left as [r1,l] and lower right as [r2,r]. Thus we can just find the subarray sum for a 1D array for each combination of rows and we would be covering all the possible submatrices.\n\n**Implementation:**\n\n```\nclass Solution {\npublic:\n    int checksub(vector<vector<int>>& matrix,int r1,int r2,int target){\n        unordered_map<int,int> m;\n        int curr=0,ans=0;\n        m[0]=1;\n\t\t//  ith element of 1D array = matrix[r2][i]-matrix[r1-1][i]\n        for(int i=0;i<matrix[0].size();i++){                  \n            if(r1>0)                    \n                curr+=matrix[r2][i]-matrix[r1-1][i];\n            else\n                curr+=matrix[r2][i];\n            \n            if(m.find(curr-target)!=m.end())\n                ans+=m[curr-target];\n            m[curr]++;\n        }\n        \n        return ans;\n    }\n    \n    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {\n        ios_base::sync_with_stdio(false);\n        cin.tie(NULL);\n        cout.tie(NULL);\n        \n        int m=matrix.size(),n=matrix[0].size();\n        if(m==0 || n==0)\n            return 0;\n        vector<vector<int>> dp(m,vector<int>(n,0));\n        for(int i=0;i<m;i++)       // Creating row prefix sum matrix\n            for(int j=0;j<n;j++){\n                if(i>0)\n                    matrix[i][j]+=matrix[i-1][j];\n            }\n        int ans=0;\n        for(int i=0;i<m;i++)     // For each row pair find 1D subarray sum with target\n            for(int j=i;j<m;j++)  \n                ans+=checksub(matrix,i,j,target);\n        return ans;\n    }\n};\n```
[]