O(N^3) Solution | C++ | Approach Fully Explained |  Must Watch
\nclass Solution {\npublic:\n    /*\n    \n    APPROACH :\n    \n    GIVEN ARRAY\n    \n    0 1 0\n    1 1 1\n    0 1 0\n    \n    no of rows(m) = 3;\n    no of
```\nclass Solution {\npublic:\n    /*\n    \n    APPROACH :\n    \n    GIVEN ARRAY\n    \n    0 1 0\n    1 1 1\n    0 1 0\n    \n    no of rows(m) = 3;\n    no of cols(n) = 4;\n    \n    First construct a prefix sum array of size {m+1 , n}\n    \n    And calculate prefix sum for every column\n    \n    Prefix Sum array\n    0 0 0\n    0 1 0\n    1 2 1\n    1 3 1\n    \n    Now for each row\n    \n        We search for all the downward sub matrics end {i,j}\n        here i>=row and i<m\n        and j>=0 and j<n\n        \n        we sum prefixSum[i+1][0] to prefixSum[i+1][j] to calulate sum of all the elements from (0,0) to (i,j) (Let Say sum)\n        we sum prefixSum[row][0] to prefixSum[row][j] to calulate sum of all the elements from (0,0) to (row-1,j) (Let Say Subsum)\n        \n        for each j\n            if we subtract sum = (sum- Subsum), we get sum of all the elements from (row,0) to (i,j)\n            \n            if(sum=target) in increase the counter\n            \n            for for this sum we check if (sum-target) exists in the map or not;\n            if exsits we can confirm that how many times we have encountered an l (0<l<j) \n                Such that\n                    sum of all the elements from (row,0) to (i,l) is (sum-target)\n                    Which indirectly confirms sum of all the elements from (row,l+1) to (i,j) is target\n                    \n            Increase mp[sum] by 1\n    \n    \n    */\n    \n    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {\n        \n        \n        int m = matrix.size();\n        int n = matrix[0].size();\n        \n        int pre[m+1][n];\n        for(int i=0;i<=m;i++){\n            for(int j=0;j<n;j++){\n                pre[i][j]=0;\n            }\n        }\n        \n        for(int j=0;j<n;j++){\n            for(int i=0;i<m;i++){\n            \n                pre[i+1][j]=pre[i][j]+matrix[i][j];\n            }\n        }\n        \n        unordered_map<int,int> mp;\n        int cnt=0;\n   /*     \n    0 0 0\n    0 1 0\n    1 2 1\n    0 3 0\n    */\n        \n        for(int row =0 ; row<m; row++){\n            \n            for(int i=row; i<m;i++){\n                mp.clear();\n                int sum=0;\n                for(int j=0; j<n;j++){\n                     sum+= pre[i+1][j]-pre[row][j];\n                    if(sum==target)\n                        cnt++;\n                    if(mp.find(sum-target)!=mp.end()){\n                        cnt+=mp[sum-target];\n                    }\n                    mp[sum]++;\n                }\n            }\n        }\n        \n        return cnt;\n    }\n};\n```
[]