Brute force and Optimised (Number of Submatrices That Sum to Target)
From Bruteforce to optimised code.\nBrute force code(TLE)\nSimply check sum of all possible (x1, y1), (x2, y2) pairs in matrix.\nWe can easily optmise this usin
From Bruteforce to optimised code.\n**Brute force code(TLE)**\nSimply check sum of all possible (x1, y1), (x2, y2) pairs in matrix.\nWe can easily optmise this using prefix 2 D array\n```\nclass Solution {\npublic:\n    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {\n        int n = matrix.size(), m = matrix[0].size();\n\n        vector<vector<int>>pre(n + 1, vector<int>(m + 1, 0));\n\n        for(int i = 1; i<=n; i++)\n            for(int j = 1; j<=m; j++)\n                pre[i][j] += pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + matrix[i-1][j-1];\n\n        int cnt = 0;\n\n        for(int i = 1; i<=n; i++) {\n            for(int j = 1; j<=m; j++) {\n                for(int k = i; k <= n; k++) {\n                    for(int l = j; l <=m; l++) {\n                        if(pre[k][l] - pre[k][j-1] - pre[i - 1][l] + pre[i - 1][j - 1] == target) {\n                            cout << k << " " << l << " " << i << " " << j << "\\n";\n                            cnt++;\n                        }\n                    }\n                }\n            }\n        }      \n\n        return cnt;\n    }\n};\n```\nBut this code leads to TLE since it is O(N^4)\n\n**Optimised approach**\nWe can iterate over all column pairs and store the prefix sum of rows between two columns.\n```\nclass Solution {\npublic:\n    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {\n        int n = matrix.size(), m = matrix[0].size();\n\n        vector<vector<int>>pre(n + 1, vector<int>(m + 1, 0));\n\n        for(int i = 1; i<=n; i++)\n            for(int j = 1; j<=m; j++)\n                pre[i][j] = matrix[i-1][j-1] + pre[i][j-1];\n\n\n        unordered_map<int, int>hsh;\n        int res = 0;\n\n        for(int col1 = 1; col1 <= m; col1++) {\n            for(int col2 = col1; col2 <= m; col2++) {\n                hsh = {{0, 1}};\n                int curr = 0;\n                for(int row = 1; row <= n; row++) {\n                    curr += pre[row][col2] - pre[row][col1 - 1];\n                    if(hsh.count(curr - target))\n                        res += hsh[curr - target];\n                    hsh[curr]++;\n                }\n            }\n        }\n        return res;\n    }\n};\n```\nTime Complexity: O(N^3)\n\nThank You \u2764\uFE0F
[]