🔥 Brute force, optimization, optimization x2
Intuition\n- Brute force is too costly\n- At 1 dimension, any range addition, can be represented as addition and reduction at left boundary and right boundary+1
# Intuition\n- Brute force is too costly\n- At 1 dimension, any range addition, can be represented as addition and reduction at left boundary and right boundary+1\n    - Whats range addition? (1d)\n    - [1,5,2] means increase each value between index 1 and 5 by 2\n        - this problem is a speicifc case, where all deltas are 1\n    - That means put 2 at index 1 and -2 at index 6(5+1, if exist) then do prefix sum\n    - multi range additions can be combined together into one array, and do one last pre fix sum\n        - why? Try it.\n- At 2 dimensions, it\'s actually the same\n- For detail regarding range addition refer to [370. Range Addition](https://leetcode.com/problems/range-addition/), from 1d to 2d\n\n\n# [Brute Force, 502ms](https://leetcode.com/problems/increment-submatrices-by-one/submissions/878740844/)\nTC: O(n^2*L), L is length of query\nSC: O(1)\n```java\nclass Solution {\n    public int[][] rangeAddQueries(int n, int[][] Q) {\n        int[][] res = new int[n][n];\n        for (var q : Q) {\n            int r0 = q[0], c0 = q[1], r1 = q[2]+1, c1 = q[3]+1;\n            for (int i = r0; i < r1; i++) for (int j = c0; j < c1; j++)\n              res[i][j]++;\n        }\n        return res;\n    }\n}\n```\n# [row level optimization, 21 ms](https://leetcode.com/problems/increment-submatrices-by-one/submissions/885321637/)\nTC: O(n*L+n^2)\nSC: O(1)\n```java\nclass Solution {\n    public int[][] rangeAddQueries(int n, int[][] queries) {\n        int[][] res = new int[n][n];\n        for (var q : queries) {\n            int r0 = q[0], c0 = q[1], r1 = q[2]+1, c1 = q[3]+1;\n            for (int i = r0; i < r1; i++) {\n                res[i][c0]++;\n                if (c1 < n) res[i][c1]--;\n            }\n        }\n\n        for (var row : res)\n            for (int j = 1; j < n; j++)\n                row[j] += row[j-1];\n\n        return res;\n    }\n}\n```\n# [2d, 7ms](https://leetcode.com/problems/increment-submatrices-by-one/submissions/885379542/)\nTC: O(2*n^2)\nSC: O(1)\n```java\nclass Solution {\n    public int[][] rangeAddQueries(int n, int[][] Q) {\n        int[][] res = new int[n][n];\n        for (var q : Q) {\n            int r0 = q[0], c0 = q[1], r1 = q[2]+1, c1 = q[3]+1;\n            res[r0][c0]++;\n            if (c1 < n) res[r0][c1]--;\n            if (r1 < n) {\n                res[r1][c0]--;\n                if (c1 < n) res[r1][c1]++;\n            }\n        }\n\n        for (int i = 0; i < n; i++) for (int j = 1; j < n; j++)\n            res[i][j] += res[i][j-1];\n\n        for (int i = 1; i < n; i++) for (int j = 0; j < n; j++)\n            res[i][j] += res[i-1][j];\n\n        return res;\n    }\n}\n```\n\nPlease ignore below unless you want to know what "not fun" is.\n# [2d, 11 ms, just for (NOT) fun](https://leetcode.com/problems/increment-submatrices-by-one/submissions/885312579/)\nTC: O(L+n^2)\nSC: O(n+L)\n```java\nclass Solution {\n    record Row (int d, int c0, int c1) {}\n    public int[][] rangeAddQueries(int n, int[][] Q) {\n        List<Row>[] rows = new List[n];\n        for (int i = 0; i < n; i++) rows[i] = new ArrayList<>();\n\n        for (var q : Q) {\n            int r0 = q[0], c0 = q[1], r1 = q[2]+1, c1 = q[3]+1;\n            rows[r0].add(new Row(1, c0, c1));\n            if (r1 < n) rows[r1].add(new Row(-1, c0, c1));\n        }\n\n        int[][] res = new int[n][n];\n        int[] diff = new int[n];\n        for (int i = 0; i < n; i++) {\n            for (var r : rows[i]) {\n                diff[r.c0] += r.d;\n                if (r.c1 < n) diff[r.c1] -= r.d;\n            }\n\n            res[i][0] = diff[0];\n            for (int j = 1; j < n; j++) res[i][j] += res[i][j-1] + diff[j];\n        }\n\n        return res;\n    }\n}\n```
['Java']