Full and Explained in Depth || Most Intuitive || [Java/JavaScript/C++/Python]
Intuition\nLeetcode 560 This is prerequisite to understand this solution, The prerequisite is must.\n\n# Approach\n1. Iterate over all possible starting rows of
# Intuition\n[Leetcode 560](https://leetcode.com/problems/subarray-sum-equals-k/solutions/4638332/beats-100-in-depth-explained-java-c-python-javascript/) *This is prerequisite to understand this solution, The prerequisite is must.*\n\n# Approach\n1. **Iterate over all possible starting rows of the submatrix:**\n    - Begin by selecting a starting row (i) from the matrix. This row will be the top row of the submatrix.\n2. **For each starting row, iterate over all possible ending rows:**\n    - Iterate over all rows below the starting row to determine the bottom row (j) of the submatrix.\n3. **Compute the sum of elements column-wise between the starting and ending rows:**\n    - Compute the sum of elements within the current submatrix by summing the elements in each column between the selected starting and ending rows.\n4. **For each sumRow, find subarrays with the target sum using a HashMap:**\n    - Use a HashMap to store the frequency of prefix sums encountered while iterating through the columns.\n    - For each sumRow (running sum of columns), check if there exists a prefix sum that, when subtracted from the current sum, equals the target.\n    - If a prefix sum exists indicating a subarray with the target sum, increment the count.\nIncrement count by the number of subarrays found in step 4:\n5. **Accumulate the count of subarrays found with the target sum across all sumRows within the current submatrix.**\n    - Repeat steps 1-5 for all combinations of starting and ending rows:\n    - Iterate over all possible combinations of starting and ending rows to consider all potential submatrices within the matrix.\n6. **Return the final count:**\n    - Iterate through all submatrices, count those with the target sum, and return the total count.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(m * n * n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\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        int[] sumRow = new int[n];\n        int count = 0;\n\n        for(int i=0; i<m; i++) {\n            Arrays.fill(sumRow, 0);\n\n            for(int j=i; j<m; j++) {\n                for(int k=0; k<n; k++) {\n                    sumRow[k] += matrix[j][k];\n                }\n                count += subArraySum(sumRow, target);\n            }\n        }\n        return count;\n    }\n\n    private int subArraySum(int[] arr, int k) {\n        int sum = 0;\n        int count = 0;\n        HashMap<Integer, Integer> map = new HashMap<>();\n        map.put(0, 1);\n\n        for(int i=0; i<arr.length; i++) {\n            sum += arr[i];\n            int rem = sum - k;\n            \n            if(map.containsKey(rem)) {\n                count += map.get(rem);\n            }\n            map.put(sum, map.getOrDefault(sum, 0)+1);\n        }\n        return count;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {\n        int m = matrix.size();\n        int n = matrix[0].size();\n        int count = 0;\n\n        for(int i = 0; i < m; i++) {\n            vector<int> sumRow(n, 0);\n\n            for(int j = i; j < m; j++) {\n                for(int k = 0; k < n; k++) {\n                    sumRow[k] += matrix[j][k];\n                }\n                count += subArraySum(sumRow, target);\n            }\n        }\n        return count;\n    }\n\nprivate:\n    int subArraySum(vector<int>& arr, int k) {\n        int sum = 0;\n        int count = 0;\n        unordered_map<int, int> map;\n        map[0] = 1;\n\n        for(int i = 0; i < arr.size(); i++) {\n            sum += arr[i];\n            int rem = sum - k;\n            \n            if(map.find(rem) != map.end()) {\n                count += map[rem];\n            }\n            map[sum] = map.find(sum) != map.end() ? map[sum] + 1 : 1;\n        }\n        return count;\n    }\n};\n```\n```Python []\nclass Solution:\n    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n        m = len(matrix)\n        n = len(matrix[0])\n        count = 0\n\n        for i in range(m):\n            sumRow = [0] * n\n\n            for j in range(i, m):\n                for k in range(n):\n                    sumRow[k] += matrix[j][k]\n                count += self.subArraySum(sumRow, target)\n                \n        return count\n\n    def subArraySum(self, arr: List[int], k: int) -> int:\n        sum_map = defaultdict(int)\n        sum_map[0] = 1\n        total_sum = 0\n        count = 0\n\n        for num in arr:\n            total_sum += num\n            rem = total_sum - k\n            \n            if rem in sum_map:\n                count += sum_map[rem]\n            sum_map[total_sum] += 1\n\n        return count\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    const subArraySum = function(arr, k) {\n        let sum = 0;\n        let count = 0;\n        const map = new Map();\n        map.set(0, 1);\n\n        for (let i = 0; i < arr.length; i++) {\n            sum += arr[i];\n            const rem = sum - k;\n\n            if (map.has(rem)) {\n                count += map.get(rem);\n            }\n            map.set(sum, (map.get(sum) || 0) + 1);\n        }\n        return count;\n    };\n\n    let count = 0;\n    const sumRow = new Array(n).fill(0);\n\n    for (let i = 0; i < m; i++) {\n        sumRow.fill(0);\n\n        for (let j = i; j < m; j++) {\n            for (let k = 0; k < n; k++) {\n                sumRow[k] += matrix[j][k];\n            }\n            count += subArraySum(sumRow, target);\n        }\n    }\n    return count;\n};\n```\n\n---\n\n\n---\n\n![5c63d377-8ef4-4beb-b09d-0edb07e09a41_1702955205.6568592.png](https://assets.leetcode.com/users/images/b0ea6ea7-d85b-4383-a554-c843827030aa_1706454604.8695092.png)\n
['Matrix', 'C++', 'Java', 'JavaScript']