1import java.util.TreeSet;
2
3class Solution {
4  
5    public int[] getBiggestThree(int[][] grid) {
6        int rows = grid.length, cols = grid[0].length;
7        // Precompute the prefix sums for the two diagonals
8        int[][] prefixSumDiag1 = new int[rows + 1][cols + 2];
9        int[][] prefixSumDiag2 = new int[rows + 1][cols + 2];
10      
11        // Calculating prefix sum for both diagonals
12        for (int i = 1; i <= rows; ++i) {
13            for (int j = 1; j <= cols; ++j) {
14                prefixSumDiag1[i][j] = prefixSumDiag1[i - 1][j - 1] + grid[i - 1][j - 1];
15                prefixSumDiag2[i][j] = prefixSumDiag2[i - 1][j + 1] + grid[i - 1][j - 1];
16            }
17        }
18      
19        // TreeSet will store the unique sums in sorted order
20        TreeSet<Integer> uniqueSums = new TreeSet<>();
21        for (int i = 1; i <= rows; ++i) {
22            for (int j = 1; j <= cols; ++j) {
23                // Calculate the limit for the size of the rhombus based on the current cell
24                int limit = Math.min(Math.min(i - 1, rows - i), Math.min(j - 1, cols - j));
25              
26                // Add the single cell value
27                uniqueSums.add(grid[i - 1][j - 1]);
28              
29                // Generate rhombus sums of increasing sizes
30                for (int k = 1; k <= limit; ++k) {
31                    int a = prefixSumDiag1[i + k][j] - prefixSumDiag1[i][j - k];
32                    int b = prefixSumDiag1[i][j + k] - prefixSumDiag1[i - k][j];
33                    int c = prefixSumDiag2[i][j - k] - prefixSumDiag2[i - k][j];
34                    int d = prefixSumDiag2[i + k][j] - prefixSumDiag2[i][j + k];
35                  
36                    // Add the rhombus sum, adjusting for the overlap
37                    uniqueSums.add(a + b + c + d - grid[i + k - 1][j - 1] - grid[i - k - 1][j - 1]);
38                }
39              
40                // Keep only the top 3 largest sums
41                while (uniqueSums.size() > 3) {
42                    uniqueSums.pollFirst();
43                }
44            }
45        }
46      
47        // Convert the TreeSet to an array
48        int[] largestSums = new int[uniqueSums.size()];
49        for (int i = 0; i < largestSums.length; ++i) {
50            largestSums[i] = uniqueSums.pollLast();
51        }
52      
53        return largestSums;
54    }
55}
56

1class Solution {
2public:
3    vector<int> getBiggestThree(vector<vector<int>>& grid) {
4        int rows = grid.size(), cols = grid[0].size();
5      
6        // Prefix sums for diagonals from top-left to bottom-right (s1)
7        // and for diagonals from top-right to bottom-left (s2)
8        vector<vector<int>> prefixSum1(rows + 1, vector<int>(cols + 2));
9        vector<vector<int>> prefixSum2(rows + 1, vector<int>(cols + 2));
10      
11        // Calculate the prefix sums for both diagonal directions.
12        for (int i = 1; i <= rows; ++i) {
13            for (int j = 1; j <= cols; ++j) {
14                prefixSum1[i][j] = prefixSum1[i - 1][j - 1] + grid[i - 1][j - 1];
15                prefixSum2[i][j] = prefixSum2[i - 1][j + 1] + grid[i - 1][j - 1];
16            }
17        }
18      
19        // Using a set to keep track of the unique rhombus sums and ensure they are sorted.
20        set<int> rhombusSums;
21      
22        // Iterate through each cell of the grid.
23        for (int i = 1; i <= rows; ++i) {
24            for (int j = 1; j <= cols; ++j) {
25                // Find the maximum possible rhombus side length from the current position.
26                int lenLimit = min({i - 1, rows - i, j - 1, cols - j});
27              
28                // Insert the single cell value as a rhombus of side length 0.
29                rhombusSums.insert(grid[i - 1][j - 1]);
30              
31                // Check all possible rhombuses starting from the current cell.
32                for (int k = 1; k <= lenLimit; ++k) {
33                    int sumA = prefixSum1[i + k][j] - prefixSum1[i][j - k];
34                    int sumB = prefixSum1[i][j + k] - prefixSum1[i - k][j];
35                    int sumC = prefixSum2[i][j - k] - prefixSum2[i - k][j];
36                    int sumD = prefixSum2[i + k][j] - prefixSum2[i][j + k];
37                  
38                    // Calculate the sum of the rhombus edges, subtract overlapping corners.
39                    rhombusSums.insert(sumA + sumB + sumC + sumD - grid[i + k - 1][j - 1] - grid[i - k - 1][j - 1]);
40                }
41              
42                // Make sure to only keep the largest three sums if there are more.
43                while (rhombusSums.size() > 3) {
44                    rhombusSums.erase(rhombusSums.begin());
45                }
46            }
47        }
48      
49        // Convert the set into a vector and reverse, as sets are in ascending order by default.
50        return vector<int>(rhombusSums.rbegin(), rhombusSums.rend());
51    }
52};
53

1//
2// The TreeSet object is a representation of a set of values, backed by a Red-Black Tree.
3// It supports efficient lookup, addition, and deletion operations, and maintains elements in sorted order.
4//
5
6// Utility functions for Red-Black Tree
7// ...
8
9let compareFn: Compare<number>;
10
11let treeRoot: RBTreeNode<number> | null = null;
12let treeSize: number = 0;
13
14// Initialization of the TreeSet
15function initializeTreeSet(collection: number[] = [], compare: Compare<number> = defaultCompare): void {
16    // Default comparison function if the user does not specify otherwise
17    function defaultCompare(l: number, r: number): number {
18        return l < r ? -1 : l > r ? 1 : 0;
19    }
20
21    compareFn = compare;
22    treeSize = 0;
23    // Construct the tree from the given collection
24    collection.forEach((val) => add(val));
25}
26
27// Returns the total number of elements in the TreeSet
28function size(): number {
29    return treeSize;
30}
31
32// Checks if a value exists in the TreeSet
33function has(val: number): boolean {
34    return !!find(val, treeRoot);
35}
36
37// Adds a value to the TreeSet if it doesn't already exist
38function add(val: number): boolean {
39    const successful: boolean = insert(val, treeRoot, null, false);
40    treeSize += successful ? 1 : 0;
41    return successful;
42}
43
44// Deletes a value from the TreeSet
45function deleteValue(val: number): boolean {
46    const deleted = deleteNode(val, treeRoot);
47    treeSize -= deleted ? 1 : 0;
48    return deleted;
49}
50
51// Finds the least element that is greater than or equal to the given value
52function ceil(val: number): number | undefined {
53    return findCeil(val, treeRoot);
54}
55
56// Finds the greatest element that is less than or equal to the given value
57function floor(val: number): number | undefined {
58    return findFloor(val, treeRoot);
59}
60
61// Finds the smallest element in the TreeSet
62function first(): number | undefined {
63    return firstNode(treeRoot)?.data;
64}
65
66// Finds the largest element in the TreeSet
67function last(): number | undefined {
68    return lastNode(treeRoot)?.data;
69}
70
71// Removes and returns the smallest element from the TreeSet
72function shift(): number | undefined {
73    const firstElement = first();
74    if (firstElement !== undefined) {
75        deleteValue(firstElement);
76    }
77    return firstElement;
78}
79
80// Removes and returns the largest element from the TreeSet
81function pop(): number | undefined {
82    const lastElement = last();
83    if (lastElement !== undefined) {
84        deleteValue(lastElement);
85    }
86    return lastElement;
87}
88
89// Iterator to traverse through all values in the TreeSet in ascending order
90function* values(): Generator<number, undefined, unknown> {
91    for (const val of inOrder(treeRoot)) {
92        yield val;
93    }
94    return undefined;
95}
96
97// ... additional functions and iterators continue here ...
98
99// Implementation details (e.g., tree rotations, insertion, deletion, etc.) for the Red-Black Tree
100// ...
101