High-Speed Solution: Outpacing 95% of Submissions with Efficient Algorithm Design
Intuition\nWhen faced with a problem involving the sum of submatrices, a common strategy is to utilize cumulative sums, which allow for the efficient computatio
# Intuition\nWhen faced with a problem involving the sum of submatrices, a common strategy is to utilize cumulative sums, which allow for the efficient computation of the sum of any submatrix. However, a brute-force approach that considers all possible submatrices can be inefficient for large matrices. To optimize, we can combine the cumulative sum technique with a hashmap to efficiently count the occurrences of sums, thus allowing us to quickly determine if a particular submatrix sum equals the target.\n\n# Approach\nPrecompute Cumulative Sums: Calculate the cumulative sum for each cell in the matrix. Each cell\'s cumulative sum represents the total sum of the submatrix starting from the top-left corner (0,0) to the current cell.\n\nIterate Over Row Pairs: Fix two rows at a time (r1 and r2). This allows us to consider submatrices between these two rows.\n\nCalculate Column Sums and Use HashMap: For each pair of fixed rows, iterate through the columns and calculate the cumulative sum for columns within these rows. Use a hashmap to store the frequency of each cumulative sum. If the current cumulative sum minus the target is found in the hashmap, it indicates the existence of a submatrix summing to the target.\n\nCounting Submatrices: For every occurrence of a sum that, when subtracted from the current cumulative sum equals the target, increment the count. This count ultimately represents the total number of submatrices summing to the target.\n\n# Complexity\nTime complexity: The time complexity is O(n*n*n), where n is the number of rows (or columns) in the square matrix. For non-square matrices with dimensions m x n, the complexity is O(m*m*n). This complexity arises from iterating over every pair of rows and computing cumulative sums for each column in each pair.\n\nSpace complexity: The space complexity is O(m*n) for storing the cumulative sums. The space used by the hashmap can be considered as O(n) in the worst case, but this does not significantly affect the overall space complexity.\n\n\n\n# Code\n```\nclass Solution:\n    def numSubmatrixSumTarget(self, matrix, target):\n        rows, cols = len(matrix), len(matrix[0])\n        count = 0\n\n        # Precompute the cumulative sum for the matrix\n        cum_sum = [[0] * (cols + 1) for _ in range(rows + 1)]\n        for r in range(rows):\n            for c in range(cols):\n                cum_sum[r+1][c+1] = cum_sum[r+1][c] + cum_sum[r][c+1] - cum_sum[r][c] + matrix[r][c]\n\n        # Use hash map to find the target sum for submatrices\n        for r1 in range(1, rows + 1):\n            for r2 in range(r1, rows + 1):\n                sum_count = {0: 1}\n                cur_sum = 0\n                for c in range(1, cols + 1):\n                    cur_sum = cum_sum[r2][c] - cum_sum[r1-1][c]\n                    count += sum_count.get(cur_sum - target, 0)\n                    sum_count[cur_sum] = sum_count.get(cur_sum, 0) + 1\n\n        return count\n\n```
['Array', 'Hash Table', 'Matrix', 'Prefix Sum', 'Python3']