🔥✅✅Beats 99.71% with Proof | Very Easy to Understand | Prefix Sum Approach✅✅🔥
Proof - Upvote if you\'re watching the proof\n\n\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nThe key intuition here is to use 
# Proof - Upvote if you\'re watching the proof\n![image.png](https://assets.leetcode.com/users/images/a16e9000-904d-49fc-a1c0-32c96ac428e0_1706415572.504636.png)\n\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe key intuition here is to use the prefix sum technique to efficiently compute the sum of submatrices. The idea is to preprocess the matrix by calculating the cumulative sum of each row. Then, for any submatrix defined by two column indices `c1` and `c2`, and two row indices `row1` and `row2`, the sum of elements in this submatrix can be computed in constant time using the prefix sum array.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Preprocess the matrix to calculate the cumulative sum for each row. This is done by iterating through each row and updating each element to be the sum of itself and the previous element in the row.\n2. Iterate over all possible pairs of column indices `c1` and `c2`.\n3. For each pair of column indices, iterate over all possible pairs of row indices `row1` and `row2`.\n4. Calculate the sum of the submatrix defined by `c1`, `c2`, `row1`, and `row2` using the preprocessed cumulative sum array.\n5. Use a HashMap to keep track of the frequency of each sum encountered so far.\n6. Check if the current sum minus the target value exists in the HashMap. If it does, increment the count by the frequency of that sum.\n7. Update the HashMap with the current sum.\n8. Return the final count as the result.\n\n# Complexity\n- Time complexity: $$O(m * n^2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n> where m is the number of rows and n is the number of columns. The nested loops iterate over all possible submatrices, and the inner loop involves constant time operations.\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n> where n is the number of columns. The space is used for the HashMap to store the frequency of sums encountered.\n# Code\n```Java []\nclass Solution {\n    public int numSubmatrixSumTarget(int[][] matrix, int target) {\n        int m = matrix.length;\n        int n = matrix[0].length;\n\n        for (int row = 0; row < m; row++) {\n            for (int col = 1; col < n; col++) {\n                matrix[row][col] += matrix[row][col - 1];\n            }\n        }\n\n        int count = 0;\n\n        for (int c1 = 0; c1 < n; c1++) {\n            for (int c2 = c1; c2 < n; c2++) {\n                Map<Integer, Integer> map = new HashMap<>();\n                map.put(0, 1);\n                int sum = 0;\n\n                for (int row = 0; row < m; row++) {\n                    sum += matrix[row][c2] - (c1 > 0 ? matrix[row][c1 - 1] : 0);\n                    count += map.getOrDefault(sum - target, 0);\n                    map.put(sum, map.getOrDefault(sum, 0) + 1);\n                }\n            }\n        }\n\n        return count;\n    }\n}\n```\n```C []\nint numSubmatrixSumTarget(int** matrix, int matrixSize, int* matrixColSize, int target) {\n    int m = matrixSize;\n    int n = *matrixColSize;\n\n    // Preprocess the matrix to calculate cumulative sum for each row\n    for (int row = 0; row < m; row++) {\n        for (int col = 1; col < n; col++) {\n            matrix[row][col] += matrix[row][col - 1];\n        }\n    }\n\n    int count = 0;\n\n    // Iterate over all possible pairs of column indices c1 and c2\n    for (int c1 = 0; c1 < n; c1++) {\n        for (int c2 = c1; c2 < n; c2++) {\n            int sum = 0;\n            int prefixSum[100]; // Assuming a maximum size for the prefix sum array\n\n            // Initialize prefix sum array\n            for (int i = 0; i < m; i++) {\n                prefixSum[i] = 0;\n            }\n\n            // Iterate over all possible pairs of row indices row1 and row2\n            for (int row = 0; row < m; row++) {\n                // Calculate the sum of the submatrix using cumulative sum\n                sum += matrix[row][c2] - (c1 > 0 ? matrix[row][c1 - 1] : 0);\n\n                // Check if the current sum minus the target exists in the prefix sum array\n                if (sum == target) {\n                    count++;\n                }\n\n                // Update the prefix sum array\n                prefixSum[row] = sum;\n\n                // Check if the (sum - target) exists in the prefix sum array\n                for (int k = 0; k < row; k++) {\n                    if (prefixSum[row] - prefixSum[k] == target) {\n                        count++;\n                    }\n                }\n            }\n        }\n    }\n\n    return count;\n}\n```\n```C++ []\nclass Solution\n{\n    public:\n    Solution()\n    {\n        cin.tie(NULL);\n        cout.tie(NULL);\n        ios_base :: sync_with_stdio(false);\n    }\n    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target)\n    {\n        int ans = 0;\n        int n = matrix.size(), m = matrix[0].size();\n        for(int left = 0 ; left < m ; left++)\n        {\n            vector<int>pre(n, 0);\n            for(int right = left ; right < m ; right++)\n            {\n                for(int i = 0 ; i<n; i++)\n                {\n                    pre[i] += matrix[i][right];\n                }\n\n                for(int i = 0 ; i<n;i++)\n                {\n                    int sum = 0;\n                    for(int j = i ; j<n; j++)\n                    {\n                        sum += pre[j];\n                        if(sum == target)\n                        {\n                            ans += 1;\n                        }\n                    }\n                }\n            }\n        }\n        return ans;\n    }\n};\n```\n```C# []\npublic class Solution {\n    public int NumSubmatrixSumTarget(int[][] matrix, int target) {\n        int m = matrix.Length;\n        int n = matrix[0].Length;\n\n        // Preprocess the matrix to calculate the cumulative sum for each row\n        for (int row = 0; row < m; row++) {\n            for (int col = 1; col < n; col++) {\n                matrix[row][col] += matrix[row][col - 1];\n            }\n        }\n\n        int count = 0;\n\n        // Iterate over all possible pairs of column indices c1 and c2\n        for (int c1 = 0; c1 < n; c1++) {\n            for (int c2 = c1; c2 < n; c2++) {\n                Dictionary<int, int> map = new Dictionary<int, int>();\n                map[0] = 1;\n                int sum = 0;\n\n                // Iterate over all possible pairs of row indices row1 and row2\n                for (int row = 0; row < m; row++) {\n                    sum += matrix[row][c2] - (c1 > 0 ? matrix[row][c1 - 1] : 0);\n                    count += map.GetValueOrDefault(sum - target, 0);\n                    map[sum] = map.GetValueOrDefault(sum, 0) + 1;\n                }\n            }\n        }\n\n        return count;\n    }\n}\n```\n```Javascript []\n/**\n * @param {number[][]} matrix\n * @param {number} target\n * @return {number}\n */\nvar numSubmatrixSumTarget = function(matrix, target) {\n    const m = matrix.length;\n    const n = matrix[0].length;\n\n    // Preprocess the matrix to calculate cumulative sum for each row\n    for (let row = 0; row < m; row++) {\n        for (let col = 1; col < n; col++) {\n            matrix[row][col] += matrix[row][col - 1];\n        }\n    }\n\n    let count = 0;\n\n    for (let c1 = 0; c1 < n; c1++) {\n        for (let c2 = c1; c2 < n; c2++) {\n            const map = new Map();\n            map.set(0, 1);\n            let sum = 0;\n\n            for (let row = 0; row < m; row++) {\n                sum += matrix[row][c2] - (c1 > 0 ? matrix[row][c1 - 1] : 0);\n                count += map.get(sum - target) || 0;\n                map.set(sum, (map.get(sum) || 0) + 1);\n            }\n        }\n    }\n\n    return count;\n};\n```\n```Typescript []\nfunction numSubmatrixSumTarget(matrix: number[][], target: number): number {\n    const m = matrix.length;\n    const n = matrix[0].length;\n\n    for (let row = 0; row < m; row++) {\n        for (let col = 1; col < n; col++) {\n            matrix[row][col] += matrix[row][col - 1];\n        }\n    }\n\n    let count = 0;\n\n    for (let c1 = 0; c1 < n; c1++) {\n        for (let c2 = c1; c2 < n; c2++) {\n            const map = new Map<number, number>();\n            map.set(0, 1);\n            let sum = 0;\n\n            for (let row = 0; row < m; row++) {\n                sum += matrix[row][c2] - (c1 > 0 ? matrix[row][c1 - 1] : 0);\n                count += map.get(sum - target) || 0;\n                map.set(sum, (map.get(sum) || 0) + 1);\n            }\n        }\n    }\n\n    return count;\n}\n```\n```Python []\nclass Solution(object):\n    def numSubmatrixSumTarget(self, matrix, target):\n        rows, cols = len(matrix), len(matrix[0])\n        prefix_sum = [[0] * (cols + 1) for _ in range(rows + 1)]\n\n        # Compute the 2D prefix sum\n        for i in range(1, rows + 1):\n            for j in range(1, cols + 1):\n                prefix_sum[i][j] = matrix[i - 1][j - 1] + prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1]\n\n        count = 0\n\n        # Iterate through all possible pairs of columns\n        for col1 in range(1, cols + 1):\n            for col2 in range(col1, cols + 1):\n                # Use a hashmap to count the number of subarrays with a given sum\n                prefix_sum_map = {0: 1}\n                current_sum = 0\n                for row in range(1, rows + 1):\n                    current_sum = prefix_sum[row][col2] - prefix_sum[row][col1 - 1]\n                    if current_sum - target in prefix_sum_map:\n                        count += prefix_sum_map[current_sum - target]\n                    if current_sum in prefix_sum_map:\n                        prefix_sum_map[current_sum] += 1\n                    else:\n                        prefix_sum_map[current_sum] = 1\n\n        return count\n```\n```Python3 []\nclass Solution:\n    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n        m, n = len(matrix), len(matrix[0])\n\n        # Step 1: Preprocess the matrix to calculate cumulative sum for each row\n        for row in range(m):\n            for col in range(1, n):\n                matrix[row][col] += matrix[row][col - 1]\n\n        count = 0\n\n        # Step 2: Iterate over all pairs of column indices c1 and c2\n        for c1 in range(n):\n            for c2 in range(c1, n):\n                # Step 3: Iterate over all pairs of row indices row1 and row2\n                prefix_sum_map = {0: 1}\n                sum_val = 0\n\n                # Step 4: Calculate the sum of submatrix using cumulative sum\n                for row in range(m):\n                    sum_val += matrix[row][c2] - (matrix[row][c1 - 1] if c1 > 0 else 0)\n\n                    # Step 5 and 6: Update count and prefix_sum_map\n                    count += prefix_sum_map.get(sum_val - target, 0)\n                    prefix_sum_map[sum_val] = prefix_sum_map.get(sum_val, 0) + 1\n\n        # Step 8: Return the final count\n        return count\n```\n# Upvote - Please\n![image.png](https://assets.leetcode.com/users/images/07e95fab-7ac0-4779-b380-bb1327102432_1706415743.4838672.png)\n
['Array', 'C', 'Prefix Sum', 'Python', 'C++', 'Java', 'TypeScript', 'Python3', 'JavaScript', 'C#']