<p>Given a <code>matrix</code>&nbsp;and a <code>target</code>, return the number of non-empty submatrices that sum to <font face="monospace">target</font>.</p>

<p>A submatrix <code>x1, y1, x2, y2</code> is the set of all cells <code>matrix[x][y]</code> with <code>x1 &lt;= x &lt;= x2</code> and <code>y1 &lt;= y &lt;= y2</code>.</p>

<p>Two submatrices <code>(x1, y1, x2, y2)</code> and <code>(x1&#39;, y1&#39;, x2&#39;, y2&#39;)</code> are different if they have some coordinate&nbsp;that is different: for example, if <code>x1 != x1&#39;</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/02/mate1.jpg" style="width: 242px; height: 242px;" />
<pre>
<strong>Input:</strong> matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
<strong>Output:</strong> 4
<strong>Explanation:</strong> The four 1x1 submatrices that only contain 0.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> matrix = [[1,-1],[-1,1]], target = 0
<strong>Output:</strong> 5
<strong>Explanation:</strong> The two 1x2 submatrices, plus the two 2x1 submatrices, plus the 2x2 submatrix.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> matrix = [[904]], target = 0
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= matrix.length &lt;= 100</code></li>
	<li><code>1 &lt;= matrix[0].length &lt;= 100</code></li>
	<li><code>-1000 &lt;= matrix[i][j] &lt;= 1000</code></li>
	<li><code>-10^8 &lt;= target &lt;= 10^8</code></li>
</ul>

class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
//         if (matrix.empty() || matrix[0].empty()) {
//         return 0;
//     }

//     int rows = matrix.size();
//     int cols = matrix[0].size();
//     int result = 0;

//     // Calculate prefix sum for each row
//     for (vector<int>& row : matrix) {
//         for (int i = 1; i < cols; ++i) {
//             row[i] += row[i - 1];
//         }
//     }

//     // Iterate through all possible pairs of columns
//     for (int col1 = 0; col1 < cols; ++col1) {
//         for (int col2 = col1; col2 < cols; ++col2) {
//             unordered_map<int, int> prefixSums;
//             prefixSums[0] = 1;  // Initialize with one occurrence of sum 0
//             int currentSum = 0;

//             // Iterate through each row
//             for (vector<int>& row : matrix) {
//                 currentSum += row[col2] - (col1 > 0 ? row[col1 - 1] : 0);
//                 result += prefixSums[currentSum - target];
//                 prefixSums[currentSum]++;
//             }
//         }
//     }

//     return result
      
      
      //Brutr force
//       int m = matrix.size();
//         int n = matrix[0].size();
        
//         int result = 0;
        
//         //Trying All possible start points (x, y)
//         for(int start_row = 0; start_row < m; start_row++) {
//             for(int start_col = 0; start_col < n; start_col++) {
                
 
//                 //Trying All possible ending points (x', y')
//                 for(int end_row = start_row; end_row < m; end_row++) {
//                     for(int end_col = start_col; end_col < n; end_col++) {

//                         //Now iterating the start points and end points
//                         int sum = 0;
//                         for(int i = start_row; i <= end_row; i++) {
//                             for(int j = start_col; j <= end_col; j++) {
//                                 sum += matrix[i][j];
//                             }
//                         }
                        
//                         if(sum == target) {
//                             result++;
//                         }
                        
//                     }
                    
//                 }
//             }
//         }
        
//         return result;
      
      
       int rows = matrix.size(); //m
        int cols = matrix[0].size(); //n
        
        //First taje the cumulative sum row-wise
        for(int row = 0; row<rows; row++) {
            for(int col = 1; col<cols; col++) {
                matrix[row][col] += matrix[row][col-1];
            }
        }
        
        //Now, you need to find the "No. of subarrays with sum k" in downward direction
        int result = 0;
        for(int startCol = 0; startCol<cols; startCol++) {
            
            for(int currCol = startCol; currCol<cols; currCol++) {
                //We need to find all sub matrices sum
                
                //Now comes the concept of "No. of subarrays with sum k"
                unordered_map<int, int> mp;
                mp[0] = 1;
                int sum = 0;
                //Go downwards row wise
                for(int row = 0; row<rows; row++) {
                    sum += matrix[row][currCol] - (startCol > 0 ? matrix[row][startCol-1] : 0);
                    
                    if(mp.count(sum-target)) {
                        result += mp[sum-target];
                    }
                    
                    mp[sum]++;
                    
                }
                
            }
        }
        
        return result;
    }
};
110815