You are given an m x n integer matrix grid​​​.

A rhombus sum is the sum of the elements that form the border of a regular rhombus shape in grid​​​. The rhombus must have the shape of a square rotated 45 degrees with each of the corners centered in a grid cell. Below is an image of four valid rhombus shapes with the corresponding colored cells that should be included in each rhombus sum:

Note that the rhombus can have an area of 0, which is depicted by the purple rhombus in the bottom right corner.

Return the biggest three distinct rhombus sums in the grid in descending order. If there are less than three distinct values, return all of them.

&nbsp;
Example 1:

Input: grid = [[3,4,5,1,3],[3,3,4,2,3],[20,30,200,40,10],[1,5,5,4,1],[4,3,2,2,5]]
Output: [228,216,211]
Explanation: The rhombus shapes for the three biggest distinct rhombus sums are depicted above.
- Blue: 20 + 3 + 200 + 5 = 228
- Red: 200 + 2 + 10 + 4 = 216
- Green: 5 + 200 + 4 + 2 = 211


Example 2:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]]
Output: [20,9,8]
Explanation: The rhombus shapes for the three biggest distinct rhombus sums are depicted above.
- Blue: 4 + 2 + 6 + 8 = 20
- Red: 9 (area 0 rhombus in the bottom right corner)
- Green: 8 (area 0 rhombus in the bottom middle)


Example 3:

Input: grid = [[7,7,7]]
Output: [7]
Explanation: All three possible rhombus sums are the same, so return [7].


&nbsp;
Constraints:


	m == grid.length
	n == grid[i].length
	1 &lt;= m, n &lt;= 50
	1 &lt;= grid[i][j] &lt;= 105


class Solution:
def getBiggestThree(self, grid: List[List[int]]) -> List[int]:
    
    def calc(l,r,u,d):
        sc=0
        c1=c2=(l+r)//2
        expand=True
        for row in range(u,d+1):
            if c1==c2:
                sc+=grid[row][c1]
            else:
                sc+=grid[row][c1]+grid[row][c2]
            
            if c1==l:
                expand=False
            
            if expand:
                c1-=1
                c2+=1
            else:
                c1+=1
                c2-=1
        return sc
        
    
    m=len(grid)
    n=len(grid[0])
    heap=[]
    for i in range(m):
        for j in range(n):
            l=r=j
            d=i
            while l>=0 and r<=n-1 and d<=m-1:
                sc=calc(l,r,i,d)
                l-=1
                r+=1
                d+=2
                if len(heap)<3:
                    if sc not in heap:
                        heapq.heappush(heap,sc)
                else:
                    if sc not in heap and sc>heap[0]:
                        heapq.heappop(heap)
                        heapq.heappush(heap,sc)
    
    heap.sort(reverse=True)
    return heap
class Solution {
    public int[] getBiggestThree(int[][] grid) {
        int end = Math.min(grid.length, grid[0].length);
        int maxThree[] = {0,0,0};
        for(int length=0; length<end; length++){
            searchBigThree(grid, maxThree, length);
        }

        Arrays.sort(maxThree);

        // If there are less than three distinct values, return all of them.
        if(maxThree[0] == 0){
            if(maxThree[1] == 0){
                return new int[]{maxThree[2]};
            }
            return new int[]{maxThree[2],maxThree[1]};
        }

        // reverse array
        maxThree[0] = maxThree[0]^maxThree[2];
        maxThree[2] = maxThree[0]^maxThree[2];
        maxThree[0] = maxThree[0]^maxThree[2];

        return maxThree;
    }

    void searchBigThree(int[][] grid, int[] maxThree, int length){
        int end = grid.length-(length==0?0: 2*length);
        int end1 = grid[0].length-(length);
        for(int start = 0; start<end; start++){
            for(int start1 = length; start1<end1; start1++){
                if(start+start1 >= length){
                    addToMaxThree(maxThree, getSum(grid, start, start1, length));
                }
            }
        }
    }

    /*
    get sum of edges of rhombus abcd
            a
           / \
          d b
           \ /
            c

    */
    int getSum(int[][] grid, int i, int j, int length){
        if(length == 0){
            return grid[i][j];
        }

        int sum = 0;
        // edge ab
        for(int it=0; it<=length; it++){
            sum = sum + grid[i+it][j+it];
        }

        // edge ad
        for(int it=1; it<=length; it++){
            sum = sum + grid[i+it][j-it];
        }

        // edge dc
        for(int it=1; it<=length; it++){
            sum = sum + grid[i+length+it][j-length+it];
        }

        // edge bc
        for(int it=1; it<length; it++){
            sum = sum + grid[i+length+it][j+length-it];
        }

        return sum;
    }

    void addToMaxThree(int[] maxThree, int num){
        // Do not add duplicate entry
        if(maxThree[0] == num || maxThree[1] == num || maxThree[2] == num ){
            return;
        }

        Arrays.sort(maxThree);

        if(maxThree[0] < num){
            maxThree[0] = num;
        }
    }
}
class Solution {
public:
    vector<int> getBiggestThree(vector<vector<int>>& grid) {

        int n = grid.size(), m = grid[0].size();
        set<int> s;

        // 1x1, 3x3, 5x5
        for (int len = 1; len <= min(m, n); len += 2) {
            for (int i = 0; i + len <= n; i ++) {
                for (int j = 0; j + len <= m; j ++) {
                    int d = len / 2;
                    if (d == 0) { s.insert(grid[i][j]); }
                    else {
                        int x = i, y = j + d;
                        long long sum = 0;
                        for (int k = 0; k < d; k ++) sum += grid[x++][y++];
                        for (int k = 0; k < d; k ++) sum += grid[x++][y--];
                        for (int k = 0; k < d; k ++) sum += grid[x--][y--];
                        for (int k = 0; k < d; k ++) sum += grid[x--][y++];
                        s.insert(sum);
                    }
                }
            }
        }

        if (s.size() < 3)
            return vector<int>(s.rbegin(), s.rend());

        return vector<int>(s.rbegin(), next(s.rbegin(), 3));
    }
};
var getBiggestThree = function(grid) {
    const m = grid.length;
    const n = grid[0].length;

    const set = new Set();

    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            let sum = grid[i][j];

            set.add(sum)

            let len = 1;
            let row = i;
            let col = j;

            while (withinBound(row + 1, col - 1)) {
                ++len;
                ++row;
                --col;

                traverse(i, j, row, col, sum, len, 0, "botRight");
                sum += grid[row][col];
            }
        }
    }

    let max1;
    let max2;
    let max3;

    for (const num of set) {
        if (max1 == null || num > max1) {
            max3 = max2;
            max2 = max1;
            max1 = num;
        }
        else if (max2 == null || num > max2) {
            max3 = max2;
            max2 = num;
        }
        else if (max3 == null || num > max3) {
            max3 = num;
        }
    }

    const res = [];

    if (max1) res[0] = max1;
    if (max2) res[1] = max2;
    if (max3) res[2] = max3;

    return res;

    function traverse(destRow, destCol, currRow, currCol, totSum, lenSize, currLen, currDir) {
        if (currRow === destRow && currCol === destCol) {
            set.add(totSum);
            return;
        }

        totSum += grid[currRow][currCol];
        ++currLen;

        if (currDir === "botRight") {
            if (currLen < lenSize) {
                if (!withinBound(currRow + 1, currCol + 1)) return;

                traverse(destRow, destCol, currRow + 1, currCol + 1, totSum, lenSize, currLen, currDir);
            }
            else if (currLen === lenSize) {
                if (!withinBound(currRow - 1, currCol + 1)) return;

                traverse(destRow, destCol, currRow - 1, currCol + 1, totSum, lenSize, 1, "topRight");
            }
        }
        else if (currDir === "topRight") {
            if (currLen < lenSize) {
                if (!withinBound(currRow - 1, currCol + 1)) return;

                traverse(destRow, destCol, currRow - 1, currCol + 1, totSum, lenSize, currLen, "topRight");
            }
            else if (currLen === lenSize) {
                if (!withinBound(currRow - 1, currCol - 1)) return;

                traverse(destRow, destCol, currRow - 1, currCol - 1, totSum, lenSize, 1, "topLeft");
            }
        }
        else if (currDir === "topLeft") {
            if (!withinBound(currRow - 1, currCol - 1)) return;

            traverse(destRow, destCol, currRow - 1, currCol - 1, totSum, lenSize, currLen, "topLeft");
        }
    }

    function withinBound(row, col) {
        return row >= 0 && col >= 0 && row < m && col < n;
    }
};
Get Biggest Three Rhombus Sums in a Grid