✅ Number of Submatrices That Sum to Target | Optimization from Brute-Force Explained!
There are a few solution mentioned by others but most have directly given the most optimal solution. Here, I will try to start from the brute-force approach and
There are a few solution mentioned by others but most have directly given the most optimal solution. Here, I will try to start from the brute-force approach and try to explain the various optimizations that can be done to finally arrive at the optimal solution.\n\n---\n\n\u274C ***Solution - I (Brute-Force Approach) [Rejected]***\n\nLet\'s start with the most basic approach to this problem. Take all the submatrices possible for the given matrix and check if their sum is equal to `target`.\n\n```\nint numSubmatrixSumTarget(vector<vector<int>>& A, int target) {\n\tint res = 0, m = size(A), n = size(A[0]);\n\t// calculate sum of each submatrix and check if it is equal to target\n\tfor(int rowStart = 0; rowStart < m; rowStart++)\n\t\tfor(int rowSize = 1; rowStart + rowSize <= m; rowSize++)\n\t\t\tfor(int colStart = 0; colStart < n; colStart++)\n\t\t\t\tfor(int colSize = 1; colStart + colSize <= n; colSize++)\n\t\t\t\t\tif(SUM(A, rowStart, rowSize, colStart, colSize) == target)\n\t\t\t\t\t\tres++;\n\treturn res;    \n}\n// Calculates the sum of a submatrix with given bounds\nint SUM(vector<vector<int> > &A, int rStart, int rSize, int cStart, int cSize){\n\tint subMatrixSum = 0;\n\tfor(int i = rStart; i < rStart + rSize; i++)\n\t\tfor(int j = cStart; j < cStart + cSize; j++)\n\t\t\tsubMatrixSum += A[i][j];\n\treturn subMatrixSum;\n}\n```\n\n***Time Complexity :*** **`O((M*N)^3)`**, where `M` is the number of rows and `N` is the number of columns  in the given matrix.\n***Space Complexity :*** **`O(1)`**\n\n---\n\n\u2714\uFE0F ***Solution - II (Compute prefix sum for each Row or Column)***\n\nWe can optimize the above approach by reducing the time complexity of the `SUM` function in the above solution. We know that in a given array, the sum of range [i,j] can be calculated by `prefixSum[j] - prefixSum[i - 1]`. We can use this to optimize the solution.\n\nAfter computing prefix sum for each row of matrix (*you can do it for column as well*), we can get the sum of a given range in O(1) time. Thus, for any submatrix of the main matrix, we just need to iterate over all its rows and we can get sum of given range (`[colStart, colEnd]`) in O(1) time.\n\n1. We just start from row 0, calculate the sum for that row for the range `[colStart, colEnd]`.\n2. Extend the sum by perform step-1 for row 1, row 2, ... and so on till last row.\n3. Repeat this process for every `[colStart, colEnd]` combination.\n\n\n```\nint numSubmatrixSumTarget(vector<vector<int>>& A, int target) {\n\tint res = 0, m = size(A), n = size(A[0]);\n\t// calculating prefix sum for each row of matrix\n\tfor (int row = 0; row < m; row++)\n\t\tfor (int col = 1; col < n; col++)\n\t\t\tA[row][col] += A[row][col - 1];\n\t// calculate sum of each submatrix and check if it is equal to target\n\tfor (int colStart = 0; colStart < n; colStart++) {\n\t\tfor (int colEnd = colStart; colEnd < n; colEnd++) {\n\t\t\tfor(int rowStart = 0; rowStart < m; rowStart++){\n\t\t\t\tint sum = 0;\n\t\t\t\tfor(int rowEnd = rowStart; rowEnd < m; rowEnd++){\n\t\t\t\t\tsum += A[rowEnd][colEnd] - (colStart ? A[rowEnd][colStart - 1] : 0);\n\t\t\t\t\tif(sum == target) res++;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\treturn res;    \n}\n```\n***Time Complexity :*** **`O((M*N)^2)`**, where `M` is the number of rows and `N` is the number of columns  in the given matrix.\n***Space Complexity :*** **`O(1)`**, since we are modifying the given matrix itself. If we use a new prefix sum matrix, the space complexity would be `O(M*N)`.\n\n---\n\n\u2714\uFE0F ***Solution - III (Further Optimization in Solution - II)***\n\nWe can further optimize the solution by using hashmap. The optimization done here is similar to the one in solution of [560. Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/solution/).\n\nBasically, we will be maintaining a running submatrix sum starting from row 0 till m, for a given `[colStart, colEnd]` range. Each sum value and number of its occurence will be stored in hashmap. If there\'s a submatrix which was found such that `cursum` at that time was equal to present sum (`cursum`) - target, then we are sure that there were occurences of submatrices which had sum equal to `target` and the count is given by `mp[cursum - target]`.\n\nIf the explanation didn\'t make the approach clear, I really suggest you to try the *560. Subarray Sum Equals K* problem and read the hashmap solution. It took me some time reading that before I was able to clearly understand this solution.\n\n```\nint numSubmatrixSumTarget(vector<vector<int>>& A, int target) {\n\tint res = 0, m = size(A), n = size(A[0]);\n\tfor (int row = 0; row < m; row++)\n\t\tfor (int col = 1; col < n; col++)\n\t\t\tA[row][col] += A[row][col - 1];\n\t//         cursum, occurences\n\tunordered_map<int, int> mp;\n\tfor (int colStart = 0; colStart < n; colStart++) {\n\t\tfor (int colEnd = colStart; colEnd < n; colEnd++) {\n\t\t\tint cursum = 0;\n\t\t\tmp = {{0, 1}};\n\t\t\tfor(int row = 0; row < m; row++){\n\t\t\t\tcursum += A[row][colEnd] - (colStart ? A[row][colStart - 1] : 0);    \n\t\t\t\t// mp[sum-target] will give number of submatrices found having sum as \'sum - target\'\n\t\t\t\tres += mp[cursum - target];\n\t\t\t\tmp[cursum]++;\n\t\t\t}\n\t\t}\n\t}\n\treturn res;    \n}\n```\n***Time Complexity :*** **`O(N*N*M)`**, where `M` is the number of rows and `N` is the number of columns  in the given matrix.\n***Space Complexity :*** **`O(N)`**\n\n\n\n---\n---\n\n\uD83D\uDCBB\uD83D\uDC31\u200D\uD83D\uDCBBIf there are any questions or mistakes in my post, please do comment below \uD83D\uDC47 \n\n---\n---
['C']