Submatrices Sum To Target: Efficient Matrix + Map Algo
Intuition\nThe intuition is to reduce the problem from 2D to 1D by using prefix sums and then apply a technique similar to "Two Sum" on the 1D array.\n Describe
# Intuition\nThe intuition is to reduce the problem from 2D to 1D by using prefix sums and then apply a technique similar to "Two Sum" on the 1D array.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. **Calculate Prefix Sums**: \nFirst, we calculate the prefix sum for each row in the `matrix`. This will help us to quickly calculate the sum of elements in any column between two rows.\n2. **Iterate Over Columns**: \nThen, we iterate over all pairs of columns and calculate the sum of elements between these two columns for every row. This effectively gives us a 1D array.\n3. **Use a Dictionary**: \nWe use a dictionary (HashMap) to keep track of the sum and its frequency. The key is the sum and the value is the frequency of this sum. We initialize the map with (0,1) because we have one submatrix (an empty one) that sums up to 0.\n4. **Check for Target Sum**: \nFor each sum, we check if `sum - target` is in the map. If it is, we add the frequency of `sum - target` to the count. This is because for each pair (i,j) where `sum[i] - sum[j] = target`, there is one more submatrix that sums up to the target.\n5. **Return Count**: \nFinally, we return the count.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(N^2 * M)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(M)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\npublic class Solution {\n    public int NumSubmatrixSumTarget(int[][] matrix, int target) {\n        int m = matrix.Length;\n        int n = matrix[0].Length;\n        for(int i = 0; i < m; i++) {\n            for(int j = 1; j < n; j++) {\n                matrix[i][j] += matrix[i][j - 1];\n            }\n        }\n\n        int count = 0;\n        for(int i = 0; i < n; i++) {\n            for(int j = i; j < n; j++) {\n                Dictionary<int, int> map = new();\n                map[0] = 1;\n                int sum = 0;\n                for(int k = 0; k < m; k++) {\n                    sum += matrix[k][j];\n                    if(i > 0)\n                        sum -= matrix[k][i - 1];\n                    if(map.ContainsKey(sum - target))\n                        count += map[sum - target];\n                    if(!map.ContainsKey(sum))\n                        map[sum] = 0;\n                    map[sum]++;\n                }\n            }\n        }\n\n        return count;\n    }\n}\n```
['Array', 'Hash Table', 'Matrix', 'Prefix Sum', 'C#']