✅☑[C++/Java/Python/JavaScript] || 2 Approaches || EXPLAINED🔥
PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n# Approaches\n(Also explained in the code)\n\n\n#### Approach 1(With Maps)\n\n1. Find the prefix sum for each row.\n1. Fo
# PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n# Approaches\n(Also explained in the code)\n\n\n#### ***Approach 1(With Maps)***\n\n1. Find the prefix sum for each row.\n1. For each pair of column find the subarrays sum eqaul to target.\n\n\n\n# Complexity\n- Time complexity:\n   $$O(m^2 * n)$$\n*(where m is the number of rows and n is the number of columns in the matrix.)*\n    \n\n- Space complexity:\n   $$O(m)$$\n    \n\n\n# Code\n```C++ []\n\n\n\nclass Solution {\npublic:\n    int numSubmatrixSumTarget(std::vector<std::vector<int>>& matrix, int target) {\n        int m = matrix.size();\n        int n = matrix[0].size();\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                std::unordered_map<int, int> map;\n                map[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[sum - target];\n                    map[sum]++;\n                }\n            }\n        }\n\n        return count;\n    }\n};\n\n\n\n\n\n```\n```Java []\n\n\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\n\n```\n```python []\nclass Solution:\n    def numSubmatrixSumTarget(self, matrix, target):\n        m, n = len(matrix), len(matrix[0])\n\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        for c1 in range(n):\n            for c2 in range(c1, n):\n                prefix_sum_count = {0: 1}\n                sum_val = 0\n\n                for row in range(m):\n                    sum_val += matrix[row][c2] - (matrix[row][c1 - 1] if c1 > 0 else 0)\n                    count += prefix_sum_count.get(sum_val - target, 0)\n                    prefix_sum_count[sum_val] = prefix_sum_count.get(sum_val, 0) + 1\n\n        return count\n\n\n```\n```javascript []\nvar numSubmatrixSumTarget = function(matrix, target) {\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();\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\n\n```\n---\n\n#### ***Approach 2(With Arrays)***\n\n1. Find the prefix sum for each row.\n1. For each pair of column find the subarrays sum eqaul to target.\n\n\n\n# Complexity\n- Time complexity:\n   $$O(m^2 * n)$$\n*(where m is the number of rows and n is the number of columns in the matrix.)*\n    \n\n- Space complexity:\n   $$O(m)$$\n    \n\n\n# Code\n```C++ []\n\nclass Solution {\npublic:\n    int subarraySum(vector<int>& nums, int k) {\n        int count=0,sum=0;\n        map<int,int>mp;\n        for(int i=0;i<nums.size();i++)\n        {\n            sum+=nums[i];\n            if(sum==k)\n            {\n                count++;\n            }\n            if(mp.find(sum-k)!=mp.end())\n            {\n             count+=mp[sum-k];  \n            }\n            mp[sum]++;\n        }\n        return count;\n    }\n    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {\n       int count=0;\n        for(int i=0; i<matrix.size(); i++){\n\t\t\t\n            vector<int> sum(matrix[0].size(), 0);\n            for(int j=i; j<matrix.size(); j++){\n                for(int k=0; k<matrix[0].size(); k++){\n                    sum[k] += matrix[j][k];\n                }\n                count += subarraySum(sum, target);\n            }\n        }\n       \n    return count;\n    }\n}; \n\n\n\n\n\n\n```\n```Java []\nimport java.util.HashMap;\nimport java.util.Map;\n\nclass Solution {\n    public int subarraySum(int[] nums, int k) {\n        int count = 0;\n        int sum = 0;\n        Map<Integer, Integer> mp = new HashMap<>();\n\n        for (int i = 0; i < nums.length; i++) {\n            sum += nums[i];\n\n            if (sum == k) {\n                count++;\n            }\n\n            if (mp.containsKey(sum - k)) {\n                count += mp.get(sum - k);\n            }\n\n            mp.put(sum, mp.getOrDefault(sum, 0) + 1);\n        }\n\n        return count;\n    }\n\n    public int numSubmatrixSumTarget(int[][] matrix, int target) {\n        int count = 0;\n\n        for (int i = 0; i < matrix.length; i++) {\n            int[] sum = new int[matrix[0].length];\n\n            for (int j = i; j < matrix.length; j++) {\n                for (int k = 0; k < matrix[0].length; k++) {\n                    sum[k] += matrix[j][k];\n                }\n\n                count += subarraySum(sum, target);\n            }\n        }\n\n        return count;\n    }\n}\n\n\n\n\n```\n```python []\nfrom typing import List\nfrom collections import defaultdict\n\nclass Solution:\n    def subarraySum(self, nums: List[int], k: int) -> int:\n        count = 0\n        sum_val = 0\n        mp = defaultdict(int)\n\n        for num in nums:\n            sum_val += num\n\n            if sum_val == k:\n                count += 1\n\n            if sum_val - k in mp:\n                count += mp[sum_val - k]\n\n            mp[sum_val] += 1\n\n        return count\n\n    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n        count = 0\n\n        for i in range(len(matrix)):\n            sum_val = [0] * len(matrix[0])\n\n            for j in range(i, len(matrix)):\n                for k in range(len(matrix[0])):\n                    sum_val[k] += matrix[j][k]\n\n                count += self.subarraySum(sum_val, target)\n\n        return count\n\n\n```\n```javascript []\nclass Solution {\n    subarraySum(nums, k) {\n        let count = 0;\n        let sum = 0;\n        const mp = new Map();\n\n        for (const num of nums) {\n            sum += num;\n\n            if (sum === k) {\n                count++;\n            }\n\n            if (mp.has(sum - k)) {\n                count += mp.get(sum - k);\n            }\n\n            mp.set(sum, (mp.get(sum) || 0) + 1);\n        }\n\n        return count;\n    }\n\n    numSubmatrixSumTarget(matrix, target) {\n        let count = 0;\n\n        for (let i = 0; i < matrix.length; i++) {\n            const sum = Array(matrix[0].length).fill(0);\n\n            for (let j = i; j < matrix.length; j++) {\n                for (let k = 0; k < matrix[0].length; k++) {\n                    sum[k] += matrix[j][k];\n                }\n\n                count += this.subarraySum(sum, target);\n            }\n        }\n\n        return count;\n    }\n}\n\n\n\n\n```\n---\n\n\n\n# PLEASE UPVOTE IF IT HELPED\n\n---\n---\n\n\n---
['Array', 'Hash Table', 'Matrix', 'Prefix Sum', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']