Get Biggest Three Rhombus Sums in a Grid
Problem
A rhombus is a square rotated 45°, with its four corners centered on grid cells. Its rhombus sum is the sum of the cells lying on its border. A rhombus may have area 0 — that is just a single cell. Enumerate every rhombus that fits inside the m × n grid, compute each border sum, and return the three largest distinct sums in descending order. If fewer than three distinct values exist, return all of them.
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]][228, 216, 211]def getBiggestThree(grid):
m, n = len(grid), len(grid[0])
sums = set() # distinct rhombus sums
for i in range(m): # top vertex row
for j in range(n): # top vertex col
k = 0 # half-diagonal length
# grow while all four corners stay in bounds
while i + 2 * k < m and j - k >= 0 and j + k < n:
if k == 0:
total = grid[i][j] # area-0 rhombus = one cell
else:
total = 0
for s in range(k): # top -> right edge
total += grid[i + s][j + s]
for s in range(k): # right -> bottom edge
total += grid[i + k + s][j + k - s]
for s in range(k): # bottom -> left edge
total += grid[i + 2 * k - s][j - s]
for s in range(k): # left -> top edge
total += grid[i + k - s][j - k + s]
sums.add(total)
k += 1
return sorted(sums, reverse=True)[:3] # three largest distinctfunction getBiggestThree(grid) {
const m = grid.length, n = grid[0].length;
const sums = new Set(); // distinct rhombus sums
for (let i = 0; i < m; i++) { // top vertex row
for (let j = 0; j < n; j++) { // top vertex col
let k = 0; // half-diagonal length
// grow while all four corners stay in bounds
while (i + 2 * k < m && j - k >= 0 && j + k < n) {
let total;
if (k === 0) {
total = grid[i][j]; // area-0 rhombus = one cell
} else {
total = 0;
for (let s = 0; s < k; s++) total += grid[i + s][j + s]; // top -> right
for (let s = 0; s < k; s++) total += grid[i + k + s][j + k - s]; // right -> bottom
for (let s = 0; s < k; s++) total += grid[i + 2 * k - s][j - s]; // bottom -> left
for (let s = 0; s < k; s++) total += grid[i + k - s][j - k + s]; // left -> top
}
sums.add(total);
k++;
}
}
}
return [...sums].sort((a, b) => b - a).slice(0, 3); // three largest distinct
}int[] getBiggestThree(int[][] grid) {
int m = grid.length, n = grid[0].length;
TreeSet<Integer> sums = new TreeSet<>(); // distinct, sorted
for (int i = 0; i < m; i++) { // top vertex row
for (int j = 0; j < n; j++) { // top vertex col
int k = 0; // half-diagonal length
// grow while all four corners stay in bounds
while (i + 2 * k < m && j - k >= 0 && j + k < n) {
int total;
if (k == 0) {
total = grid[i][j]; // area-0 = one cell
} else {
total = 0;
for (int s = 0; s < k; s++) total += grid[i + s][j + s]; // top -> right
for (int s = 0; s < k; s++) total += grid[i + k + s][j + k - s]; // right -> bottom
for (int s = 0; s < k; s++) total += grid[i + 2 * k - s][j - s]; // bottom -> left
for (int s = 0; s < k; s++) total += grid[i + k - s][j - k + s]; // left -> top
}
sums.add(total);
k++;
}
}
}
int take = Math.min(3, sums.size());
int[] res = new int[take];
for (int t = 0; t < take; t++) res[t] = sums.pollLast(); // largest first
return res;
}vector<int> getBiggestThree(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
set<int> sums; // distinct, sorted ascending
for (int i = 0; i < m; i++) { // top vertex row
for (int j = 0; j < n; j++) { // top vertex col
int k = 0; // half-diagonal length
// grow while all four corners stay in bounds
while (i + 2 * k < m && j - k >= 0 && j + k < n) {
int total;
if (k == 0) {
total = grid[i][j]; // area-0 = one cell
} else {
total = 0;
for (int s = 0; s < k; s++) total += grid[i + s][j + s]; // top -> right
for (int s = 0; s < k; s++) total += grid[i + k + s][j + k - s]; // right -> bottom
for (int s = 0; s < k; s++) total += grid[i + 2 * k - s][j - s]; // bottom -> left
for (int s = 0; s < k; s++) total += grid[i + k - s][j - k + s]; // left -> top
}
sums.insert(total);
k++;
}
}
}
vector<int> res(sums.rbegin(), sums.rend()); // descending
if (res.size() > 3) res.resize(3);
return res;
}Explanation
This is a brute-force enumeration bounded by tiny limits (m, n ≤ 50), so we can afford to look at every rhombus the grid can hold and just collect the border sums.
A rhombus is fixed by two things: its top vertex (i, j) and its half-diagonal k. From the top vertex the other three corners sit at (i+k, j+k) (right), (i+2k, j) (bottom) and (i+k, j−k) (left). The rhombus is valid only while all four corners are inside the grid, which is exactly i+2k < m, j−k ≥ 0 and j+k < n.
For k = 0 the rhombus collapses to a single cell, so its sum is just grid[i][j] — the problem explicitly allows these area-0 rhombi. For k ≥ 1 we walk the four edges. Each edge runs corner-to-corner but we stop one cell short of the next corner, so every border cell is counted exactly once and no corner is double-added.
Every total goes into a set, which both removes duplicates and lets us pick the three largest distinct values. Python sorts the set descending and slices three; Java uses a TreeSet and polls the largest three; C++ reads a set in reverse. If fewer than three distinct sums exist, we simply return all of them.
You only ever need the top three, so a bounded max-heap (or three running maxima) would save memory on huge grids — but with these constraints a sorted set is clean and plenty fast.