Super prefix sum
2 min readMay 29, 2021
We know that by using prefix sum, we can improve the range sum calculation from O(n) to O(1).
1878. Get Biggest Three Rhombus Sums in a Grid
In this week’s biweekly contest, we have a super prefix sum practise.
If we want to compute the sum of the edge elements, we can use Diagonal and anti-Diagonal prefix sum
Code
The following code has the complexity of O(m*n*max(m, n)).
int dia[100][100], anti_dia[100][100];
class Solution {
public:
vector<int> getBiggestThree(vector<vector<int>>& grid) {
memset(dia, 0, sizeof dia);
memset(anti_dia, 0, sizeof anti_dia);
const int m = grid.size(), n = grid[0].size();
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
dia[i][j] = dia[i-1][j+1] + grid[i-1][j-1];
anti_dia[i][j] = anti_dia[i-1][j-1] + grid[i-1][j-1];
}
}
set<int> ret;
for (int i = 1; i <= m; ++i){
for (int j = 1; j <= n; ++j) {
ret.insert(grid[i-1][j-1]);
if (ret.size()>3) ret.erase(ret.begin());
for (int d = 1; i - d >= 1 && i + d <= m && j + d <= n && j - d >=1; d++) {
int this_ret = 0;
int ai = i - d, aj = j, di = i + d, dj = j, bi = i, bj = j - d, ci = i, cj = j + d;
/*
a
b c
d
*/
// ab + dc
this_ret += dia[bi][bj] - dia[ai-1][aj+1] + dia[di][dj] - dia[ci-1][cj+1];
// bd + ac
this_ret += anti_dia[di][dj] - anti_dia[bi-1][bj-1] + anti_dia[ci][cj] - anti_dia[ai-1][aj-1];
this_ret -= grid[ai-1][aj-1] + grid[bi - 1][bj - 1] + grid[ci - 1][cj - 1] + grid[di - 1][dj - 1];
ret.insert(this_ret);
if (ret.size()>3) ret.erase(ret.begin());
}
}
}
return vector<int>(ret.rbegin(), ret.rend());
}
};
Thanks for reading.