1878. Get Biggest Three Rhombus Sums in a Grid

/**
 * Problem: LeetCode 1878 - Get Biggest Three Rhombus Sums in a Grid
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.TreeSet;

class Solution {
    public int[] getBiggestThree(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        TreeSet<Integer> set = new TreeSet<>();

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                // Area 0 rhombus (single cell)
                set.add(grid[r][c]);

                // Area > 0 rhombuses with radius L
                for (int L = 1; r - L >= 0 && r + L < m && c - L >= 0 && c + L < n; L++) {
                    int sum = 0;
                    for (int i = 0; i < L; i++) {
                        sum += grid[r - L + i][c + i];     // top to right
                        sum += grid[r + i][c + L - i];     // right to bottom
                        sum += grid[r + L - i][c - i];     // bottom to left
                        sum += grid[r - i][c - L + i];     // left to top
                    }
                    set.add(sum);
                }
            }
        }

        int count = Math.min(3, set.size());
        int[] result = new int[count];
        for (int i = 0; i < count; i++) {
            result[i] = set.pollLast();
        }
        return result;
    }
}

"""
Problem: LeetCode 1878 - Get Biggest Three Rhombus Sums in a Grid
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
from typing import List


class Solution:

    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:
        m = len(grid)
        n = len(grid[0])
        sums = set()

        for r in range(m):
            for c in range(n):
                # Area 0 rhombus
                sums.add(grid[r][c])

                # Area > 0 rhombuses with radius L
                L = 1
                while r - L >= 0 and r + L < m and c - L >= 0 and c + L < n:
                    total = 0
                    for i in range(L):
                        total += grid[r - L + i][c + i]  # top to right
                        total += grid[r + i][c + L - i]  # right to bottom
                        total += grid[r + L - i][c - i]  # bottom to left
                        total += grid[r - i][c - L + i]  # left to top
                    sums.add(total)
                    L += 1

        return sorted(sums, reverse=True)[:3]

/**
 * Problem: LeetCode 1878 - Get Biggest Three Rhombus Sums in a Grid
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> getBiggestThree(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        set<int> sums;

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                // Area 0 rhombus
                sums.insert(grid[r][c]);

                // Area > 0 rhombuses with radius L
                for (int L = 1; r - L >= 0 && r + L < m && c - L >= 0 && c + L < n; L++) {
                    int sum = 0;
                    for (int i = 0; i < L; i++) {
                        sum += grid[r - L + i][c + i];     // top to right
                        sum += grid[r + i][c + L - i];     // right to bottom
                        sum += grid[r + L - i][c - i];     // bottom to left
                        sum += grid[r - i][c - L + i];     // left to top
                    }
                    sums.insert(sum);
                }
            }
        }

        vector<int> result;
        for (auto it = sums.rbegin(); it != sums.rend() && result.size() < 3; ++it) {
            result.push_back(*it);
        }
        return result;
    }
};

/**
 * Problem: LeetCode 1878 - Get Biggest Three Rhombus Sums in a Grid
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number[][]} grid
 * @return {number[]}
 */
var getBiggestThree = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    const sums = new Set();

    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            // Area 0 rhombus
            sums.add(grid[r][c]);

            // Area > 0 rhombuses with radius L
            for (let L = 1; r - L >= 0 && r + L < m && c - L >= 0 && c + L < n; L++) {
                let sum = 0;
                for (let i = 0; i < L; i++) {
                    sum += grid[r - L + i][c + i];     // top to right
                    sum += grid[r + i][c + L - i];     // right to bottom
                    sum += grid[r + L - i][c - i];     // bottom to left
                    sum += grid[r - i][c - L + i];     // left to top
                }
                sums.add(sum);
            }
        }
    }

    const sorted = Array.from(sums).sort((a, b) => b - a);
    return sorted.slice(0, 3);
};