# Super prefix sum

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());      }};`

Data Scientist/MLE/SWE @takemobi

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi