Get Biggest Three Rhombus Sums in a Grid — Solution
Get Biggest Three Rhombus Sums in a Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Get Biggest Three Rhombus Sums in a Grid is a medium coding problem on arrays, sorting and matrix, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Matrix, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an m x n integer matrix grid. A rhombus is a square rotated 45° whose four corners sit at the centres of grid cells; a single cell counts as a rhombus of size 0. A rhombus with top corner (i, j) and size k has its other corners at (i+k, j+k), (i+2k, j) and (i+k, j-k), and must lie entirely inside the grid.
The rhombus sum is the sum of the cells on the rhombus's border only (the cells its four edges pass through), not the cells inside.
Return the biggest three distinct rhombus sums in descending order. If there are fewer than three distinct values, return all of them.
Example 1
Input: grid = [[5,1,2],[3,9,4],[1,6,7]]
Output: [14,9,7]
Explanation: The only rhombus of size 1 passes through 1, 4, 6 and 3 for a sum of 14; the largest single cells are 9 and 7.
Example 2
Input: grid = [[4,4,4]]
Output: [4]
Explanation: Every rhombus sum is 4, and duplicates count once.
Example 3
Input: grid = [[3,8]]
Output: [8,3]
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 501 <= grid[i][j] <= 10^5
Hints for Get Biggest Three Rhombus Sums in a Grid
Hint 1
A rhombus is fixed by its top cell
(i, j)and its sizek; it fits wheni + 2k < m,j - k >= 0andj + k < n.Hint 2
Its border has exactly
4kcells (1 whenk = 0): walk the four edges, eachksteps, without counting a corner twice.Hint 3
Keep only the three largest distinct sums seen so far — no need to store them all.
How to solve Get Biggest Three Rhombus Sums in a Grid
Enumerate every rhombus by top corner and size, sum its border by walking four diagonal edges, and keep a running top-three of distinct values.
Approach
- For each cell
(i, j), offergrid[i][j](the size-0 rhombus). - For
k = 1, 2, …whilei + 2k < m,j - k >= 0andj + k < n: fortfrom 0 tok - 1addgrid[i+t][j+t](top→right),grid[i+k+t][j+k-t](right→bottom),grid[i+2k-t][j-t](bottom→left) andgrid[i+k-t][j-k+t](left→top). - Offer the sum to the top-three list: ignore it if already present, otherwise insert it in order and drop anything beyond three.
- Return the list.
Why it works
Each edge walk starts at one corner and stops just before the next, so the four walks cover the 4k border cells exactly once. Every rhombus inside the grid has a unique top corner and size, so all of them are offered, and the bounded list keeps exactly the three largest distinct values.
Complexity
- Time —
O(m · n · min(m, n)²) — diagonal prefix sums bring it to O(m · n · min(m, n)) - Space —
O(1)
Pitfalls
- Corners belong to two edges; walk each edge half-open so they are counted once.
- Sums must be distinct — equal sums from different rhombi count once.
- A single cell is a valid rhombus of size 0.
Reference solution
Python
from typing import List
def getBiggestThree(grid: List[List[int]]) -> List[int]:
m, n = len(grid), len(grid[0])
top = []
def offer(v):
if v in top:
return
top.append(v)
top.sort(reverse=True)
if len(top) > 3:
top.pop()
for i in range(m):
for j in range(n):
offer(grid[i][j])
k = 1
while i + 2 * k < m and j - k >= 0 and j + k < n:
s = 0
for t in range(k):
s += grid[i + t][j + t]
s += grid[i + k + t][j + k - t]
s += grid[i + 2 * k - t][j - t]
s += grid[i + k - t][j - k + t]
offer(s)
k += 1
return topJava
public static int[] getBiggestThree(int[][] grid) {
int m = grid.length, n = grid[0].length;
TreeSet<Integer> top = new TreeSet<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
top.add(grid[i][j]);
if (top.size() > 3) top.pollFirst();
for (int k = 1; i + 2 * k < m && j - k >= 0 && j + k < n; k++) {
int s = 0;
for (int t = 0; t < k; t++) {
s += grid[i + t][j + t];
s += grid[i + k + t][j + k - t];
s += grid[i + 2 * k - t][j - t];
s += grid[i + k - t][j - k + t];
}
top.add(s);
if (top.size() > 3) top.pollFirst();
}
}
}
int[] out = new int[top.size()];
int idx = 0;
for (int v : top.descendingSet()) out[idx++] = v;
return out;
}C++
vector<int> getBiggestThree(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
set<int> top;
auto offer = [&](int v) {
top.insert(v);
if (top.size() > 3) top.erase(top.begin());
};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
offer(grid[i][j]);
for (int k = 1; i + 2 * k < m && j - k >= 0 && j + k < n; k++) {
int s = 0;
for (int t = 0; t < k; t++) {
s += grid[i + t][j + t];
s += grid[i + k + t][j + k - t];
s += grid[i + 2 * k - t][j - t];
s += grid[i + k - t][j - k + t];
}
offer(s);
}
}
}
return vector<int>(top.rbegin(), top.rend());
}JavaScript
var getBiggestThree = function(grid) {
var m = grid.length, n = grid[0].length, top = [];
var offer = function(v) {
if (top.indexOf(v) >= 0) return;
top.push(v);
top.sort(function(a, b) { return b - a; });
if (top.length > 3) top.pop();
};
for (var i = 0; i < m; i++) {
for (var j = 0; j < n; j++) {
offer(grid[i][j]);
for (var k = 1; i + 2 * k < m && j - k >= 0 && j + k < n; k++) {
var s = 0;
for (var t = 0; t < k; t++) {
s += grid[i + t][j + t];
s += grid[i + k + t][j + k - t];
s += grid[i + 2 * k - t][j - t];
s += grid[i + k - t][j - k + t];
}
offer(s);
}
}
}
return top;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms