Get Biggest Three Rhombus Sums in a Grid solution and explanation

def rhombusSum(grid, x, y, s):
    if x - s < 0 or x + s >= len(grid) or y - s < 0 or y + s >= len(grid[0]):
        return float('-inf')
    if s == 0:
        return grid[x][y]
    rhombus_sum = 0
    for i in range(s):
        rhombus_sum += grid[x - s + i][y + i]
        rhombus_sum += grid[x + s - i][y + i]
        rhombus_sum += grid[x - s + i][y - i]
        rhombus_sum += grid[x + s - i][y - i]
    rhombus_sum -= (grid[x - s][y] + grid[x + s][y] + grid[x][y + s] + grid[x][y - s])
    return rhombus_sum + grid[x][y]

def getBiggestThreeRhombusSums(grid):
    rhombus_sums = set()
    m, n = len(grid), len(grid[0])
    for i in range(m):
        for j in range(n):
            for size in range((min(m, n) // 2) + 1):
                sum = rhombusSum(grid, i, j, size)
                if sum != float('-inf'):
                    rhombus_sums.add(sum)
    result = sorted(rhombus_sums, reverse=True)
    return result[:3]

if __name__ == "__main__":
    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]
    ]
    print(getBiggestThreeRhombusSums(grid))

import java.util.*;

class Solution {
    public static int rhombusSum(int[][] grid, int x, int y, int s) {
        if (x - s < 0 || x + s >= grid.length || y - s < 0 || y + s >= grid[0].length) return Integer.MIN_VALUE;
        int sum = 0;
        if (s == 0) return grid[x][y];
        for (int i = 0; i < s; i++) {
            sum += grid[x - s + i][y + i];
            sum += grid[x + s - i][y + i];
            sum += grid[x - s + i][y - i];
            sum += grid[x + s - i][y - i];
        }
        sum -= (grid[x - s][y] + grid[x + s][y] + grid[x][y + s] + grid[x][y - s]);
        return sum + grid[x][y];
    }

    public static int[] getBiggestThreeRhombusSums(int[][] grid) {
        Set<Integer> sums = new TreeSet<>(Collections.reverseOrder());
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int s = 0; s <= Math.min(m, n) / 2; s++) {
                    int sum = rhombusSum(grid, i, j, s);
                    if (sum != Integer.MIN_VALUE) sums.add(sum);
                }
            }
        }

        int[] result = new int[Math.min(3, sums.size())];
        int index = 0;
        for (int sum : sums) {
            if (index < result.length) result[index++] = sum;
            else break;
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] 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}
        };
        System.out.println(Arrays.toString(getBiggestThreeRhombusSums(grid)));
    }
}

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int rhombusSum(const vector<vector<int>>& grid, int x, int y, int s, int m, int n) {
    if (x - s < 0 || x + s >= m || y - s < 0 || y + s >= n) return INT_MIN;
    int sum = 0;
    if (s == 0) return grid[x][y];
    for (int i = 0; i < s; i++) {
        sum += grid[x - s + i][y + i];
        sum += grid[x + s - i][y + i];
        sum += grid[x - s + i][y - i];
        sum += grid[x + s - i][y - i];
    }
    sum -= (grid[x - s][y] + grid[x + s][y] + grid[x][y + s] + grid[x][y - s]);
    return sum + grid[x][y];
}

vector<int> getBiggestThreeRhombusSums(vector<vector<int>>& grid) {
    set<int, greater<int>> distinctSums;
    int m = grid.size(), n = grid[0].size();
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            for (int s = 0; s <= min(m, n) / 2; s++) {
                int sum = rhombusSum(grid, i, j, s, m, n);
                if (sum != INT_MIN) distinctSums.insert(sum);
            }
        }
    }

    vector<int> result;
    for (auto it = distinctSums.begin(); it != distinctSums.end() && result.size() < 3; ++it) {
        result.push_back(*it);
    }
    return result;
}

int main() {
    vector<vector<int>> 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}};
    vector<int> result = getBiggestThreeRhombusSums(grid);
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

function rhombusSum(grid, x, y, size) {
    if (x - size < 0 || x + size >= grid.length || y - size < 0 || y + size >= grid[0].length) return -Infinity;
    let sum = 0;
    if (size === 0) return grid[x][y];
    for (let i = 0; i < size; i++) {
        sum += grid[x - size + i][y + i];
        sum += grid[x + size - i][y + i];
        sum += grid[x - size + i][y - i];
        sum += grid[x + size - i][y - i];
    }
    sum -= grid[x - size][y];
    sum -= grid[x + size][y];
    sum -= grid[x][y + size];
    sum -= grid[x][y - size];
    return sum + grid[x][y];
}

function getBiggestThreeRhombusSums(grid) {
    const distinctSums = new Set();
    const m = grid.length, n = grid[0].length;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            for (let size = 0; size <= Math.min(m, n) / 2; size++) {
                const sum = rhombusSum(grid, i, j, size);
                if (sum !== -Infinity) distinctSums.add(sum);
            }
        }
    }
    const results = Array.from(distinctSums).sort((a, b) => b - a);
    return results.slice(0, 3);
}

const 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]
];
console.log(getBiggestThreeRhombusSums(grid));

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int min(int a, int b) { return a < b ? a : b; }

void addDistinctSum(int *sums, int *size, int newSum) {
    for (int i = 0; i < *size; i++) {
        if (sums[i] == newSum) return;
    }
    sums[(*size)++] = newSum;    
}

int rhombusSum(int **grid, int m, int n, int x, int y, int size) {
    if (x - size < 0 || x + size >= m || y - size < 0 || y + size >= n) return INT_MIN;
    int sum = 0;
    if (size == 0) return grid[x][y];
    for (int i = 0; i < size; i++) {
        sum += grid[x - size + i][y + i];
        sum += grid[x + size - i][y + i];
        sum += grid[x - size + i][y - i];
        sum += grid[x + size - i][y - i];
    }
    sum -= grid[x - size][y];
    sum -= grid[x + size][y];
    sum -= grid[x][y + size];
    sum -= grid[x][y - size];
    return sum + grid[x][y];
}

void findTopThreeSums(int m, int n, int **grid, int *result) {
    int *sums = (int *)malloc(m * n * sizeof(int));
    int index = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            for (int size = 0; size <= min(m, n) / 2; size++) {
                int sum = rhombusSum(grid, m, n, i, j, size);
                if (sum != INT_MIN) addDistinctSum(sums, &index, sum);
            }
        }
    }

    int arrLength = index;
    for (int i = 0; i < 3 && i < arrLength; i++) {
        int max = -1, maxIndex = -1;
        for (int j = 0; j < arrLength; j++) {
            if (sums[j] > max) {
                max = sums[j];
                maxIndex = j;
            }
        }
        result[i] = max;
        sums[maxIndex] = -1;
    }

    free(sums);
}

int main() {
    int grid[5][5] = {{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}};
    int m = 5, n = 5;
    int **gridPtr = (int **)malloc(m * sizeof(int *));
    for (int i = 0; i < m; i++) {
        gridPtr[i] = grid[i];
    }

    int result[3];
    findTopThreeSums(m, n, gridPtr, result);
    printf("%d %d %d\n", result[0], result[1], result[2]);

    free(gridPtr);
    return 0;
}

using System;
using System.Collections.Generic;

class Solution {
    public static int RhombusSum(int[][] grid, int x, int y, int size) {
        if (x - size < 0 || x + size >= grid.Length || y - size < 0 || y + size >= grid[0].Length) return int.MinValue;
        int sum = 0;
        if (size == 0) return grid[x][y];
        for (int i = 0; i < size; i++) {
            sum += grid[x - size + i][y + i];
            sum += grid[x + size - i][y + i];
            sum += grid[x - size + i][y - i];
            sum += grid[x + size - i][y - i];
        }
        sum -= grid[x - size][y];
        sum -= grid[x + size][y];
        sum -= grid[x][y + size];
        sum -= grid[x][y - size];
        return sum + grid[x][y];
    }

    public static int[] GetBiggestThreeRhombusSums(int[][] grid) {
        HashSet<int> sums = new HashSet<int>();
        int m = grid.Length, n = grid[0].Length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int size = 0; size <= Math.Min(m, n) / 2; size++) {
                    int sum = RhombusSum(grid, i, j, size);
                    if (sum != int.MinValue) sums.Add(sum);
                }
            }
        }

        List<int> list = new List<int>(sums);
        list.Sort((a, b) => b.CompareTo(a));
        return list.GetRange(0, Math.Min(3, list.Count)).ToArray();
    }

    public static void Main(string[] args) {
        int[][] grid = {
            new int[] {3, 4, 5, 1, 3},
            new int[] {3, 3, 4, 2, 3},
            new int[] {20, 30, 200, 40, 10},
            new int[] {1, 5, 5, 4, 1},
            new int[] {4, 3, 2, 2, 5}
        };
        int[] result = GetBiggestThreeRhombusSums(grid);
        Console.WriteLine(string.Join(", ", result));
    }
}

def build_prefix_sum(grid):
    m, n = len(grid), len(grid[0])
    prefix = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            prefix[i][j] = grid[i][j]
            if i > 0:
                prefix[i][j] += prefix[i-1][j]
            if j > 0:
                prefix[i][j] += prefix[i][j-1]
            if i > 0 and j > 0:
                prefix[i][j] -= prefix[i-1][j-1]
    return prefix

def rhombus_sum_from_prefix(prefix, x, y, size):
    # Implement calculation from precomputed prefix sums
    return 0

def getBiggestThreeRhombusSums(grid):
    # Utilizes build_prefix_sum in main execution
    pass

if __name__ == '__main__':
    print("Python Precomputation approach conceptual example.")

import java.util.*;

class Solution {
    public static void main(String[] args) {
        System.out.println("Java Precomputation approach conceptual example.");
    }
}

#include <iostream>
#include <vector>
#include <set>
using namespace std;

vector<vector<int>> buildPrefixSum(const vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> prefix(m, vector<int>(n, 0));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            prefix[i][j] = grid[i][j];
            if (i > 0) prefix[i][j] += prefix[i-1][j];
            if (j > 0) prefix[i][j] += prefix[i][j-1];
            if (i > 0 && j > 0) prefix[i][j] -= prefix[i-1][j-1];
        }
    }
    return prefix;
}

int rhombusSumFromPrefix(const vector<vector<int>>& prefix, int x, int y, int s) {
    // This function conceptually uses prefix,
    // Implement sum calculation based on prefix precomputation here
    // Placeholder return
    return 0;
}

int main() {
    cout << "C++ Precomputation approach conceptual example." << endl;
    return 0;
}

console.log('JavaScript Precomputation approach conceptual example.');

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

// Note: This solution is conceptual and would need helpers similar to the approach described
// such as prefix sums or other precomputation optimizations

int main() {
    printf("C Precomputation approach is conceptual for demonstration.");
    return 0;
}

using System;

class Program {
    public static void Main(string[] args) {
        Console.WriteLine("C# Precomputation approach conceptual example.");
    }
}

function getBiggestThree(grid: number[][]): number[] {
    const m = grid.length;
    const n = grid[0].length;
    const s1: number[][] = Array.from({ length: m + 1 }, () => Array(n + 2).fill(0));
    const s2: number[][] = Array.from({ length: m + 1 }, () => Array(n + 2).fill(0));
    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            s1[i][j] = s1[i - 1][j - 1] + grid[i - 1][j - 1];
            s2[i][j] = s2[i - 1][j + 1] + grid[i - 1][j - 1];
        }
    }
    const ss = new TreeSet<number>();
    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            const l = Math.min(i - 1, m - i, j - 1, n - j);
            ss.add(grid[i - 1][j - 1]);
            for (let k = 1; k <= l; ++k) {
                const a = s1[i + k][j] - s1[i][j - k];
                const b = s1[i][j + k] - s1[i - k][j];
                const c = s2[i][j - k] - s2[i - k][j];
                const d = s2[i + k][j] - s2[i][j + k];
                ss.add(a + b + c + d - grid[i + k - 1][j - 1] + grid[i - k - 1][j - 1]);
            }
            while (ss.size() > 3) {
                ss.shift();
            }
        }
    }
    return [...ss].reverse();
}

type Compare<T> = (lhs: T, rhs: T) => number;

class RBTreeNode<T = number> {
    data: T;
    count: number;
    left: RBTreeNode<T> | null;
    right: RBTreeNode<T> | null;
    parent: RBTreeNode<T> | null;
    color: number;
    constructor(data: T) {
        this.data = data;
        this.left = this.right = this.parent = null;
        this.color = 0;
        this.count = 1;
    }

    sibling(): RBTreeNode<T> | null {
        if (!this.parent) return null; // sibling null if no parent
        return this.isOnLeft() ? this.parent.right : this.parent.left;
    }

    isOnLeft(): boolean {
        return this === this.parent!.left;
    }

    hasRedChild(): boolean {
        return (
            Boolean(this.left && this.left.color === 0) ||
            Boolean(this.right && this.right.color === 0)
        );
    }
}

class RBTree<T> {
    root: RBTreeNode<T> | null;
    lt: (l: T, r: T) => boolean;
    constructor(compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0)) {
        this.root = null;
        this.lt = (l: T, r: T) => compare(l, r) < 0;
    }

    rotateLeft(pt: RBTreeNode<T>): void {
        const right = pt.right!;
        pt.right = right.left;

        if (pt.right) pt.right.parent = pt;
        right.parent = pt.parent;

        if (!pt.parent) this.root = right;
        else if (pt === pt.parent.left) pt.parent.left = right;
        else pt.parent.right = right;

        right.left = pt;
        pt.parent = right;
    }

    rotateRight(pt: RBTreeNode<T>): void {
        const left = pt.left!;
        pt.left = left.right;

        if (pt.left) pt.left.parent = pt;
        left.parent = pt.parent;

        if (!pt.parent) this.root = left;
        else if (pt === pt.parent.left) pt.parent.left = left;
        else pt.parent.right = left;

        left.right = pt;
        pt.parent = left;
    }

    swapColor(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
        const tmp = p1.color;
        p1.color = p2.color;
        p2.color = tmp;
    }

    swapData(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
        const tmp = p1.data;
        p1.data = p2.data;
        p2.data = tmp;
    }

    fixAfterInsert(pt: RBTreeNode<T>): void {
        let parent = null;
        let grandParent = null;

        while (pt !== this.root && pt.color !== 1 && pt.parent?.color === 0) {
            parent = pt.parent;
            grandParent = pt.parent.parent;

            /*  Case : A
                Parent of pt is left child of Grand-parent of pt */
            if (parent === grandParent?.left) {
                const uncle = grandParent.right;

                /* Case : 1
                   The uncle of pt is also red
                   Only Recoloring required */
                if (uncle && uncle.color === 0) {
                    grandParent.color = 0;
                    parent.color = 1;
                    uncle.color = 1;
                    pt = grandParent;
                } else {
                    /* Case : 2
                       pt is right child of its parent
                       Left-rotation required */
                    if (pt === parent.right) {
                        this.rotateLeft(parent);
                        pt = parent;
                        parent = pt.parent;
                    }

                    /* Case : 3
                       pt is left child of its parent
                       Right-rotation required */
                    this.rotateRight(grandParent);
                    this.swapColor(parent!, grandParent);
                    pt = parent!;
                }
            } else {
                /* Case : B
               Parent of pt is right child of Grand-parent of pt */
                const uncle = grandParent!.left;

                /*  Case : 1
                    The uncle of pt is also red
                    Only Recoloring required */
                if (uncle != null && uncle.color === 0) {
                    grandParent!.color = 0;
                    parent.color = 1;
                    uncle.color = 1;
                    pt = grandParent!;
                } else {
                    /* Case : 2
                       pt is left child of its parent
                       Right-rotation required */
                    if (pt === parent.left) {
                        this.rotateRight(parent);
                        pt = parent;
                        parent = pt.parent;
                    }

                    /* Case : 3
                       pt is right child of its parent
                       Left-rotation required */
                    this.rotateLeft(grandParent!);
                    this.swapColor(parent!, grandParent!);
                    pt = parent!;
                }
            }
        }
        this.root!.color = 1;
    }

    delete(val: T): boolean {
        const node = this.find(val);
        if (!node) return false;
        node.count--;
        if (!node.count) this.deleteNode(node);
        return true;
    }

    deleteAll(val: T): boolean {
        const node = this.find(val);
        if (!node) return false;
        this.deleteNode(node);
        return true;
    }

    deleteNode(v: RBTreeNode<T>): void {
        const u = BSTreplace(v);

        // True when u and v are both black
        const uvBlack = (u === null || u.color === 1) && v.color === 1;
        const parent = v.parent!;

        if (!u) {
            // u is null therefore v is leaf
            if (v === this.root) this.root = null;
            // v is root, making root null
            else {
                if (uvBlack) {
                    // u and v both black
                    // v is leaf, fix double black at v
                    this.fixDoubleBlack(v);
                } else {
                    // u or v is red
                    if (v.sibling()) {
                        // sibling is not null, make it red"
                        v.sibling()!.color = 0;
                    }
                }
                // delete v from the tree
                if (v.isOnLeft()) parent.left = null;
                else parent.right = null;
            }
            return;
        }

        if (!v.left || !v.right) {
            // v has 1 child
            if (v === this.root) {
                // v is root, assign the value of u to v, and delete u
                v.data = u.data;
                v.left = v.right = null;
            } else {
                // Detach v from tree and move u up
                if (v.isOnLeft()) parent.left = u;
                else parent.right = u;
                u.parent = parent;
                if (uvBlack) this.fixDoubleBlack(u);
                // u and v both black, fix double black at u
                else u.color = 1; // u or v red, color u black
            }
            return;
        }

        // v has 2 children, swap data with successor and recurse
        this.swapData(u, v);
        this.deleteNode(u);

        // find node that replaces a deleted node in BST
        function BSTreplace(x: RBTreeNode<T>): RBTreeNode<T> | null {
            // when node have 2 children
            if (x.left && x.right) return successor(x.right);
            // when leaf
            if (!x.left && !x.right) return null;
            // when single child
            return x.left ?? x.right;
        }
        // find node that do not have a left child
        // in the subtree of the given node
        function successor(x: RBTreeNode<T>): RBTreeNode<T> {
            let temp = x;
            while (temp.left) temp = temp.left;
            return temp;
        }
    }

    fixDoubleBlack(x: RBTreeNode<T>): void {
        if (x === this.root) return; // Reached root

        const sibling = x.sibling();
        const parent = x.parent!;
        if (!sibling) {
            // No sibiling, double black pushed up
            this.fixDoubleBlack(parent);
        } else {
            if (sibling.color === 0) {
                // Sibling red
                parent.color = 0;
                sibling.color = 1;
                if (sibling.isOnLeft()) this.rotateRight(parent);
                // left case
                else this.rotateLeft(parent); // right case
                this.fixDoubleBlack(x);
            } else {
                // Sibling black
                if (sibling.hasRedChild()) {
                    // at least 1 red children
                    if (sibling.left && sibling.left.color === 0) {
                        if (sibling.isOnLeft()) {
                            // left left
                            sibling.left.color = sibling.color;
                            sibling.color = parent.color;
                            this.rotateRight(parent);
                        } else {
                            // right left
                            sibling.left.color = parent.color;
                            this.rotateRight(sibling);
                            this.rotateLeft(parent);
                        }
                    } else {
                        if (sibling.isOnLeft()) {
                            // left right
                            sibling.right!.color = parent.color;
                            this.rotateLeft(sibling);
                            this.rotateRight(parent);
                        } else {
                            // right right
                            sibling.right!.color = sibling.color;
                            sibling.color = parent.color;
                            this.rotateLeft(parent);
                        }
                    }
                    parent.color = 1;
                } else {
                    // 2 black children
                    sibling.color = 0;
                    if (parent.color === 1) this.fixDoubleBlack(parent);
                    else parent.color = 1;
                }
            }
        }
    }

    insert(data: T): boolean {
        // search for a position to insert
        let parent = this.root;
        while (parent) {
            if (this.lt(data, parent.data)) {
                if (!parent.left) break;
                else parent = parent.left;
            } else if (this.lt(parent.data, data)) {
                if (!parent.right) break;
                else parent = parent.right;
            } else break;
        }

        // insert node into parent
        const node = new RBTreeNode(data);
        if (!parent) this.root = node;
        else if (this.lt(node.data, parent.data)) parent.left = node;
        else if (this.lt(parent.data, node.data)) parent.right = node;
        else {
            parent.count++;
            return false;
        }
        node.parent = parent;
        this.fixAfterInsert(node);
        return true;
    }

    find(data: T): RBTreeNode<T> | null {
        let p = this.root;
        while (p) {
            if (this.lt(data, p.data)) {
                p = p.left;
            } else if (this.lt(p.data, data)) {
                p = p.right;
            } else break;
        }
        return p ?? null;
    }

    *inOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
        if (!root) return;
        for (const v of this.inOrder(root.left!)) yield v;
        yield root.data;
        for (const v of this.inOrder(root.right!)) yield v;
    }

    *reverseInOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
        if (!root) return;
        for (const v of this.reverseInOrder(root.right!)) yield v;
        yield root.data;
        for (const v of this.reverseInOrder(root.left!)) yield v;
    }
}

class TreeSet<T = number> {
    _size: number;
    tree: RBTree<T>;
    compare: Compare<T>;
    constructor(
        collection: T[] | Compare<T> = [],
        compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
    ) {
        if (typeof collection === 'function') {
            compare = collection;
            collection = [];
        }
        this._size = 0;
        this.compare = compare;
        this.tree = new RBTree(compare);
        for (const val of collection) this.add(val);
    }

    size(): number {
        return this._size;
    }

    has(val: T): boolean {
        return !!this.tree.find(val);
    }

    add(val: T): boolean {
        const successful = this.tree.insert(val);
        this._size += successful ? 1 : 0;
        return successful;
    }

    delete(val: T): boolean {
        const deleted = this.tree.deleteAll(val);
        this._size -= deleted ? 1 : 0;
        return deleted;
    }

    ceil(val: T): T | undefined {
        let p = this.tree.root;
        let higher = null;
        while (p) {
            if (this.compare(p.data, val) >= 0) {
                higher = p;
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return higher?.data;
    }

    floor(val: T): T | undefined {
        let p = this.tree.root;
        let lower = null;
        while (p) {
            if (this.compare(val, p.data) >= 0) {
                lower = p;
                p = p.right;
            } else {
                p = p.left;
            }
        }
        return lower?.data;
    }

    higher(val: T): T | undefined {
        let p = this.tree.root;
        let higher = null;
        while (p) {
            if (this.compare(val, p.data) < 0) {
                higher = p;
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return higher?.data;
    }

    lower(val: T): T | undefined {
        let p = this.tree.root;
        let lower = null;
        while (p) {
            if (this.compare(p.data, val) < 0) {
                lower = p;
                p = p.right;
            } else {
                p = p.left;
            }
        }
        return lower?.data;
    }

    first(): T | undefined {
        return this.tree.inOrder().next().value;
    }

    last(): T | undefined {
        return this.tree.reverseInOrder().next().value;
    }

    shift(): T | undefined {
        const first = this.first();
        if (first === undefined) return undefined;
        this.delete(first);
        return first;
    }

    pop(): T | undefined {
        const last = this.last();
        if (last === undefined) return undefined;
        this.delete(last);
        return last;
    }

    *[Symbol.iterator](): Generator<T, void, void> {
        for (const val of this.values()) yield val;
    }

    *keys(): Generator<T, void, void> {
        for (const val of this.values()) yield val;
    }

    *values(): Generator<T, undefined, void> {
        for (const val of this.tree.inOrder()) yield val;
        return undefined;
    }

    /**
     * Return a generator for reverse order traversing the set
     */
    *rvalues(): Generator<T, undefined, void> {
        for (const val of this.tree.reverseInOrder()) yield val;
        return undefined;
    }
}

class TreeMultiSet<T = number> {
    _size: number;
    tree: RBTree<T>;
    compare: Compare<T>;
    constructor(
        collection: T[] | Compare<T> = [],
        compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
    ) {
        if (typeof collection === 'function') {
            compare = collection;
            collection = [];
        }
        this._size = 0;
        this.compare = compare;
        this.tree = new RBTree(compare);
        for (const val of collection) this.add(val);
    }

    size(): number {
        return this._size;
    }

    has(val: T): boolean {
        return !!this.tree.find(val);
    }

    add(val: T): boolean {
        const successful = this.tree.insert(val);
        this._size++;
        return successful;
    }

    delete(val: T): boolean {
        const successful = this.tree.delete(val);
        if (!successful) return false;
        this._size--;
        return true;
    }

    count(val: T): number {
        const node = this.tree.find(val);
        return node ? node.count : 0;
    }

    ceil(val: T): T | undefined {
        let p = this.tree.root;
        let higher = null;
        while (p) {
            if (this.compare(p.data, val) >= 0) {
                higher = p;
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return higher?.data;
    }

    floor(val: T): T | undefined {
        let p = this.tree.root;
        let lower = null;
        while (p) {
            if (this.compare(val, p.data) >= 0) {
                lower = p;
                p = p.right;
            } else {
                p = p.left;
            }
        }
        return lower?.data;
    }

    higher(val: T): T | undefined {
        let p = this.tree.root;
        let higher = null;
        while (p) {
            if (this.compare(val, p.data) < 0) {
                higher = p;
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return higher?.data;
    }

    lower(val: T): T | undefined {
        let p = this.tree.root;
        let lower = null;
        while (p) {
            if (this.compare(p.data, val) < 0) {
                lower = p;
                p = p.right;
            } else {
                p = p.left;
            }
        }
        return lower?.data;
    }

    first(): T | undefined {
        return this.tree.inOrder().next().value;
    }

    last(): T | undefined {
        return this.tree.reverseInOrder().next().value;
    }

    shift(): T | undefined {
        const first = this.first();
        if (first === undefined) return undefined;
        this.delete(first);
        return first;
    }

    pop(): T | undefined {
        const last = this.last();
        if (last === undefined) return undefined;
        this.delete(last);
        return last;
    }

    *[Symbol.iterator](): Generator<T, void, void> {
        yield* this.values();
    }

    *keys(): Generator<T, void, void> {
        for (const val of this.values()) yield val;
    }

    *values(): Generator<T, undefined, void> {
        for (const val of this.tree.inOrder()) {
            let count = this.count(val);
            while (count--) yield val;
        }
        return undefined;
    }

    /**
     * Return a generator for reverse order traversing the multi-set
     */
    *rvalues(): Generator<T, undefined, void> {
        for (const val of this.tree.reverseInOrder()) {
            let count = this.count(val);
            while (count--) yield val;
        }
        return undefined;
    }
}

func getBiggestThree(grid [][]int) []int {
	m, n := len(grid), len(grid[0])
	s1 := make([][]int, m+1)
	s2 := make([][]int, m+1)
	for i := range s1 {
		s1[i] = make([]int, n+2)
		s2[i] = make([]int, n+2)
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			s1[i][j] = s1[i-1][j-1] + grid[i-1][j-1]
			s2[i][j] = s2[i-1][j+1] + grid[i-1][j-1]
		}
	}

	ss := treemap.NewWithIntComparator()
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			l := min(i-1, m-i, j-1, n-j)
			ss.Put(grid[i-1][j-1], nil)
			for k := 1; k <= l; k++ {
				a := s1[i+k][j] - s1[i][j-k]
				b := s1[i][j+k] - s1[i-k][j]
				c := s2[i][j-k] - s2[i-k][j]
				d := s2[i+k][j] - s2[i][j+k]
				ss.Put(a+b+c+d-grid[i+k-1][j-1]+grid[i-k-1][j-1], nil)
			}
			for ss.Size() > 3 {
				x, _ := ss.Min()
				ss.Remove(x.(int))
			}
		}
	}
	ans := make([]int, ss.Size())
	for i, k := range ss.Keys() {
		ans[len(ans)-i-1] = k.(int)
	}
	return ans
}

use std::collections::BTreeSet;

impl Solution {
    pub fn get_biggest_three(grid: Vec<Vec<i32>>) -> Vec<i32> {
        let m = grid.len();
        let n = grid[0].len();

        let mut s1 = vec![vec![0; n + 2]; m + 1];
        let mut s2 = vec![vec![0; n + 2]; m + 1];

        for i in 1..=m {
            for j in 1..=n {
                s1[i][j] = s1[i - 1][j - 1] + grid[i - 1][j - 1];
                s2[i][j] = s2[i - 1][j + 1] + grid[i - 1][j - 1];
            }
        }

        let mut ss = BTreeSet::new();

        for i in 1..=m {
            for j in 1..=n {
                let l = (i - 1)
                    .min(m - i)
                    .min(j - 1)
                    .min(n - j);

                ss.insert(grid[i - 1][j - 1]);

                for k in 1..=l {
                    let a = s1[i + k][j] - s1[i][j - k];
                    let b = s1[i][j + k] - s1[i - k][j];
                    let c = s2[i][j - k] - s2[i - k][j];
                    let d = s2[i + k][j] - s2[i][j + k];

                    let v = a + b + c + d
                        - grid[i + k - 1][j - 1]
                        + grid[i - k - 1][j - 1];

                    ss.insert(v);
                }

                while ss.len() > 3 {
                    let first = *ss.iter().next().unwrap();
                    ss.remove(&first);
                }
            }
        }

        let mut ans = Vec::with_capacity(ss.len());
        while let Some(&v) = ss.iter().next_back() {
            ans.push(v);
            ss.remove(&v);
        }

        ans
    }
}