From O(N^4) to O(N^3)
O(N^4):\n Enumerate all (r0, r1, c0, c1) pairs. Each variable is 1 layer in a nested loop. With 4 levels of loop, complexity gets to O(N^4).\n\nO(N^3):\n Enumer
O(N^4):\n* Enumerate all (r0, r1, c0, c1) pairs. Each variable is 1 layer in a nested loop. With 4 levels of loop, complexity gets to O(N^4).\n\nO(N^3):\n* Enumerate all (c0, c1) pairs. This gives O(N^2) complexity.\n* Then, for a pair, we get a sub-slice of the matrix. We compute the prefix-sum that says (what\'s the sum of the first `r` rows in the slice?) and convert this into "find a subsequence that sums to a certain target" problem. This can be solved in O(N) by storing all prefix sums into a hash table.\n* In total, the O(N) loop is nested in the O(N^2) loop, giving O(N^3) overall.\n\nIn the following code, setting variable `SLOW` to true gives O(N^4). Setting it to false gives O(N^3).\n\n(However I was not debugging fast enough so I could not submit the solution before the end of the context X_X )\n\n```\nclass Solution {\npublic:\n    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {\n        const int R = int(matrix.size()), C = int(matrix[0].size());\n\t\tint the_sum = 0;\n\n        for (int r=0; r<R; r++) {\n            for (int c=0; c<C; c++) {\n\t\t\t\tthe_sum += int(abs(matrix[r][c]));\n                if (c>0) matrix[r][c] += matrix[r][c-1];\n            }\n        }\n\n\t\tif (target > the_sum) return 0;\n\t\tif (target < -the_sum)return 0;\n        \n        for (int r=0; r<R; r++) {\n            for (int c=0; c<C; c++) {\n                if (r>0) matrix[r][c] += matrix[r-1][c];\n            }\n        }\n        \n        if (0) {\n            for (int r=0; r<R; r++) {\n                for (int c=0; c<C; c++) {\n                    printf("%d ", matrix[r][c]);\n                }\n                printf("\\n");\n            }\n        }\n        \n        int ret = 0;\n\n\t\tconst bool SLOW = false;\n\t\tif (SLOW) {\n\t\t\tfor (int r0=0; r0<R; r0++) {\n\t\t\t\tfor (int c0=0; c0<C; c0++) {\n\t\t\t\t\tfor (int r1=r0; r1<R; r1++) {\n\t\t\t\t\t\tfor (int c1=c0; c1<C; c1++) {\n\t\t\t\t\t\t\tint x = matrix[r1][c1];\n\t\t\t\t\t\t\tif (r0>0) x -= matrix[r0-1][c1];\n\t\t\t\t\t\t\tif (c0>0) x -= matrix[r1][c0-1];\n\t\t\t\t\t\t\tif (r0>0 && c0>0) x += matrix[r0-1][c0-1];\n\t\t\t\t\t\t\t//printf("[%d,%d,%d,%d] = %d\\n", r0,c0,r1,c1,x);\n\t\t\t\t\t\t\tif (x == target) {\n\t\t\t\t\t\t\t\tret++;\n\t\t\t\t\t\t\t}\n\t\t\t\t\t\t}\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\n\t\t} else {\n\t\t\tfor (int c0 = 0; c0 < C; c0 ++) {\n\t\t\t\tfor (int c1 = c0; c1 < C; c1 ++) {\n\t\t\t\t\tunordered_map<int, int> prefix_sums;\n\t\t\t\t\tfor (int r=0; r<R; r++) {\n\t\t\t\t\t\tint curr = matrix[r][c1];\n\t\t\t\t\t\tif (c0 > 0) curr -= matrix[r][c0-1];\n\t\t\t\t\n\t\t\t\t\t\tint key = -(target - curr);\n\t\t\t\t\t\tif (prefix_sums.find(key) != prefix_sums.end()) {\n\t\t\t\t\t\t\tret += prefix_sums[key];\n\t\t\t\t\t\t}\n//\t\t\t\t\t\tprintf("Cols[%d,%d] Rows[0,%d] sum=%d, key=%d\\n", c0, c1, r, curr, key);\n\t\t\t\t\t\tif (curr == target) ret ++;\n\n\t\t\t\t\t\tprefix_sums[curr] ++;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\n\t\t}\n        return ret;\n    }\n};\n\n```\n
[]