✅☑Beats 99.59% Users || Easy Understood Solution with optimized space || 2 Approaches🔥
\n\n# Explanation :- \n\n1. Prefix Sum Calculation:\n   - Calculate the prefix sum for each row in the matrix. This is done to efficiently compute the sum of an
![Screenshot 2024-01-25 12924d.PNG](https://assets.leetcode.com/users/images/93269dd4-2041-4a87-9f70-b6f4993def0b_1706479949.7410514.png)\n\n# Explanation :- \n\n1. Prefix Sum Calculation:\n   - Calculate the prefix sum for each row in the matrix. This is done to efficiently compute the sum of any subarray in constant time.\n2. Iterating Over Column Pairs:\n   - Iterate over all possible pairs of columns (start_col and end_col).\n3. Cumulative Sum Calculation:\n   - For each pair of columns, iterate over each row and calculate the cumulative sum of elements between start_col and end_col.\n4. Using Dictionary for Prefix Sums:\n   - Use a dictionary (prefix_sum_count) to store the count of prefix sums encountered so far.\n5. Counting Submatrices:\n   - Check if the complement of the current sum (current_sum - target) exists in the dictionary. If yes, add its count to the result.\n6. Updating Dictionary:\n   - Update the dictionary with the current cumulative sum.\n7. Final Result:\n   - Return the total count of submatrices with a sum equal to the target value.\n#  brute-force approach \n   - Time Complexity: O(rows^2 * cols^2).\n```\nclass Solution:\n    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n        rows, cols = len(matrix), len(matrix[0])\n        result = 0\n\n        # Iterate over all possible submatrices\n        for top_row in range(rows):\n            for bottom_row in range(top_row, rows):\n                for left_col in range(cols):\n                    for right_col in range(left_col, cols):\n                        # Calculate the sum of the current submatrix\n                        current_sum = 0\n                        for i in range(top_row, bottom_row + 1):\n                            for j in range(left_col, right_col + 1):\n                                current_sum += matrix[i][j]\n\n                        # Check if the sum is equal to the target\n                        if current_sum == target:\n                            result += 1\n\n        return result\n\n```\n# Complexity\n- Time complexity:  O(cols^2 * rows)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(rows)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n# code 1 \n  - (T.c & S.c:  O(col^2 * row))\n```\nclass Solution:\n    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n        row, col = len(matrix), len(matrix[0])\n        res = 0\n\n        # Update cumulative sums for each column in the matrix\n        for i in range(row):\n            for j in range(1, col):\n                matrix[i][j] += matrix[i][j-1]\n\n        # Iterate through all possible combinations of start and end columns\n        for s_col in range(col):\n            for l_col in range(s_col, col):\n                # Dictionary to store cumulative sums and their frequencies\n                h = {0: 1}\n                cums = 0\n                for i in range(row):\n                    # Calculate the cumulative sum for the current submatrix\n                    cums += matrix[i][l_col] - (matrix[i][s_col-1] if s_col > 0 else 0)\n                    \n                    # If the difference between current cumulative sum and target exists in dictionary,\n                    # increment the result count by the frequency of that difference\n                    if cums - target in h:\n                        res += h[cums - target]\n                    \n                    # Update the dictionary with the current cumulative sum\n                    h[cums] = h.get(cums, 0) + 1\n\n        return res\n\n```\n# Code 2\n```\nclass Solution:\n    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n        rows, cols = len(matrix), len(matrix[0])\n\n        # Calculate the prefix sum for each row\n        for row in matrix:\n            for j in range(1, cols):\n                row[j] += row[j - 1]\n\n        result = 0\n\n        # Iterate over all possible pairs of columns\n        for start_col in range(cols):\n            for end_col in range(start_col, cols):\n                # Use a dictionary to store the prefix sum of subarrays in each row\n                prefix_sum_count = {0: 1}\n                current_sum = 0\n\n                # Iterate over each row and calculate the cumulative sum\n                for row in matrix:\n                    current_sum += row[end_col] - (row[start_col - 1] if start_col > 0 else 0)\n\n                    # Check if the complement (current_sum - target) exists in prefix_sum_count\n                    complement = current_sum - target\n                    result += prefix_sum_count.get(complement, 0)\n\n                    # Update the prefix_sum_count dictionary\n                    prefix_sum_count[current_sum] = prefix_sum_count.get(current_sum, 0) + 1\n\n        return result\n        \n```\n![leetcode up1.png](https://assets.leetcode.com/users/images/ddb3e8e1-2a8d-4d03-84d9-b1dc81b88e0b_1706479871.3280435.jpeg)\n
['Array', 'Hash Table', 'Ordered Map', 'Rolling Hash', 'Matrix', 'Counting', 'Hash Function', 'Prefix Sum', 'Python', 'Python3']