C# Solution for Number of Submatrices That Sum To Target Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition behind this solution is to use prefix sums and a hashmap to efficiently f
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition behind this solution is to use prefix sums and a hashmap to efficiently find submatrices with the target sum. By iterating over all possible pairs of columns and treating the problem as a one-dimensional array problem along the rows, the solution aims to optimize the counting process.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tPrecompute the prefix sum for each row in the matrix, similar to the Java solution.\n2.\tIterate over all possible pairs of columns (left and right) to form a potential submatrix.\n3.\tFor each pair of columns, iterate over all rows and calculate the sum of the submatrix between those columns.\n4.\tUse a dictionary (Dictionary<int, int>) to keep track of the prefix sums encountered so far. Update the dictionary as you iterate over the rows.\n5.\tCheck if the current prefix sum minus the target is present in the dictionary. If yes, update the count accordingly.\n6.\tReturn the final count as the result.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nLet m be the number of rows and n be the number of columns. The double nested loops over columns and rows contribute O(n^2 * m) time complexity. The dictionary operations inside the loops take O(1) time. Overall, the time complexity is O(n^2 * m).\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is O(m) for the dictionary used to store prefix sums. Additionally, there are some constant space variables. Therefore, the overall space complexity is O(m). The space complexity is kept low by using a dictionary to store prefix sums instead of a nested hashm\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        int result = 0;\n\n        // Precompute the prefix sum for each row\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        // Iterate over all possible column pairs\n        for (int left = 0; left < n; left++) {\n            for (int right = left; right < n; right++) {\n                int currentSum = 0;\n                Dictionary<int, int> prefixSumCount = new Dictionary<int, int>();\n                prefixSumCount[0] = 1;\n\n                // Iterate over all rows to calculate the submatrix sum\n                for (int row = 0; row < m; row++) {\n                    int rowSum = matrix[row][right] - (left > 0 ? matrix[row][left - 1] : 0);\n                    currentSum += rowSum;\n\n                    // Check if there is a submatrix with the target sum\n                    if (prefixSumCount.ContainsKey(currentSum - target)) {\n                        result += prefixSumCount[currentSum - target];\n                    }\n\n                    // Update the prefix sum count\n                    if (prefixSumCount.ContainsKey(currentSum)) {\n                        prefixSumCount[currentSum]++;\n                    } else {\n                        prefixSumCount[currentSum] = 1;\n                    }\n                }\n            }\n        }\n\n        return result;\n    }\n}\n```
['C#']