Get Biggest Three Rhombus Sums in a Grid

Get Biggest Three Rhombus Sums in a Grid

What is this problem about?

The Get Biggest Three Rhombus Sums in a Grid interview question gives you a 2D integer matrix. A "rhombus sum" is the sum of all elements that lie on the border of a rhombus shape within the grid. The rhombus can be of any size (including a single cell, which has an area of 0 but a sum equal to its value). You need to find all distinct rhombus sums and return the top three largest ones in descending order. If there are fewer than three distinct sums, return all of them.

Why is this asked in interviews?

Companies like Uber and Capital One ask the Get Biggest Three Rhombus Sums in a Grid coding problem to test your ability to handle complex matrix traversals. It evaluates your spatial reasoning and whether you can iterate over diagonal borders efficiently. It's a "Medium" problem that tests if you can keep track of maximum values (using a heap or sorted set) while exhaustively exploring geometric shapes in a grid.

Algorithmic pattern used

This problem relies on Matrix Traversal and Prefix Sums (Optional).

1. Iteration: Iterate over every cell (i, j) to treat it as the top vertex of a potential rhombus.
2. Expansion: For a chosen top vertex, expand the "size" k of the rhombus (from 0 up to the boundary limits).
3. Calculation: Calculate the sum of the border elements for that specific rhombus. For size 0, it's just grid[i][j]. For size > 0, trace the four diagonal sides.
4. Tracking Top 3: Use a Set to store distinct sums, and keep track of the largest three (or use a Min-Heap of size 3).

Example explanation

Grid:

[3, 4, 5]
[2, 7, 1]
[8, 9, 2]

1. Size 0 Rhombuses: Just single cells. Sums: 3, 4, 5, 2, 7, etc. Max so far: 9.
2. Size 1 Rhombuses: Let top vertex be at (0, 1) which is 4.
   • Left vertex: (1, 0) is 2.
   • Right vertex: (1, 2) is 1.
   • Bottom vertex: (2, 1) is 9.
   • Sum = 4 + 2 + 1 + 9 = 16.
3. Store 16. Continue searching. Return the 3 largest unique sums found.

Common mistakes candidates make

• Counting Interior Elements: Summing the entire area of the rhombus instead of just the border cells.
• Index Out of Bounds: Expanding k too far and attempting to access cells outside the grid matrix.
• Not Handling Duplicates: Failing to return distinct sums (e.g., returning [10, 10, 8] instead of [10, 8, 7]).

Interview preparation tip

When tracing diagonal borders, it's easy to accidentally double-count the vertices (top, bottom, left, right). Be careful with your loop ranges to ensure each vertex is added exactly once.