💥C# | Runtime 111 ms Beats 100.00%, Memory 53.15 MB Beats 76.19% [EXPLAINED]
Intuition\nI want to find all submatrices in a grid that sum up to a given target. To do this efficiently, I first need to understand how to quickly compute the
# Intuition\nI want to find all submatrices in a grid that sum up to a given target. To do this efficiently, I first need to understand how to quickly compute the sum of any submatrix.\n\n# Approach\nPrefix Sums: Calculate vertical prefix sums for quick submatrix sum calculations.\n\nRow Pairs: Iterate through pairs of rows to find submatrices.\n\nHash Map: Use a hash map to track prefix sums and count submatrices that match the target\n\n# Complexity\n- Time complexity:\nO(r^2 * c).\n\n- Space complexity:\nO(c).\n\n# Code\n```csharp []\npublic class Solution {\n    // Time O(r^2 * c) | Space O(c), where r = number of rows, c = number of columns\n    public int NumSubmatrixSumTarget(int[][] matrix, int target) {\n        int rows = matrix.Length, cols = matrix[0].Length, result = 0;\n\n        // Compute prefix sums vertically for each column\n        for (int r = 1; r < rows; r++) {\n            for (int c = 0; c < cols; c++) {\n                matrix[r][c] += matrix[r - 1][c];\n            }\n        }\n\n        var sumFreq = new Dictionary<int, int>();\n\n        // Iterate over all pairs of rows\n        for (int r1 = 0; r1 < rows; r1++) {\n            for (int r2 = r1; r2 < rows; r2++) {\n                // Calculate the prefix sums for columns in the current row range\n                int[] combinedSum = new int[cols];\n                for (int c = 0; c < cols; c++) {\n                    int rowSum = matrix[r2][c] - (r1 > 0 ? matrix[r1 - 1][c] : 0);\n                    combinedSum[c] = rowSum + (c > 0 ? combinedSum[c - 1] : 0);\n                }\n\n                // Count submatrices with the target sum\n                sumFreq.Clear();\n                sumFreq[0] = 1;  // Base case\n                for (int c = 0; c < cols; c++) {\n                    int runningSum = combinedSum[c];\n                    int targetSum = runningSum - target;\n                    if (sumFreq.TryGetValue(targetSum, out int freq)) {\n                        result += freq;\n                    }\n                    sumFreq[runningSum] = sumFreq.GetValueOrDefault(runningSum, 0) + 1;\n                }\n            }\n        }\n        return result;\n    }\n}\n\n```
['C#']