Get Biggest Three Rhombus Sums in a Grid

You are given an m x n grid of integers. A rhombus sum is the sum of the elements that form the border of a regular rhombus shape in the grid. The rhombus must have its diagonals aligned with the row and column axes. A rhombus of "size 0" is just a single cell. Return the biggest three distinct rhombus sums in the grid, sorted in descending order. If there are fewer than three distinct values, return all of them.

This is LeetCode 1878: Get Biggest Three Rhombus Sums in a Grid, and it tests your ability to enumerate geometric shapes inside a 2D matrix and extract border elements efficiently.

The approach is to try every possible center cell in the grid and, for each center, try every valid rhombus size. For a given center (r, c) and size s, the rhombus extends s rows up, s rows down, s columns left, and s columns right. The maximum valid size depends on the distance from the center to the nearest edge. For each valid rhombus, walk the four edges of the diamond shape, sum up the border values, and add that sum to a collection. A size-0 rhombus is just the cell value itself. After processing all centers and sizes, sort the collected distinct sums and return the top three.

The code

def getBiggestThree(grid: list[list[int]]) -> list[int]:
    m, n = len(grid), len(grid[0])
    sums = set()

    for r in range(m):
        for c in range(n):
            sums.add(grid[r][c])
            max_size = min(r, m - 1 - r, c, n - 1 - c)
            for s in range(1, max_size + 1):
                total = 0
                for i in range(s):
                    total += grid[r - s + i][c + i]
                    total += grid[r + i][c + s - i]
                    total += grid[r + s - i][c - i]
                    total += grid[r - i][c - s + i]
                sums.add(total)

    return sorted(sums, reverse=True)[:3]

The outer two loops pick every cell (r, c) as a potential center. The cell value itself is always added to the set as the size-0 case. Then max_size is the largest rhombus that fits without going out of bounds, computed as the minimum distance from the center to any edge.

For each size s, the inner loop walks the four sides of the rhombus border. Each iteration of i visits one cell on each of the four sides. The four expressions correspond to the top-right edge, the right-bottom edge, the bottom-left edge, and the left-top edge of the diamond. Because each corner is visited by two adjacent sides, the loop range range(s) is set up so that each corner is counted exactly once.

Using a set for sums ensures that only distinct values are tracked. At the end, sorting the set in descending order and slicing the first three elements gives the answer.

Visual walkthrough

The walkthrough shows the two types of rhombus: size 0 (a single cell) and size 1 (four border cells forming a diamond). For larger grids, size 2 and beyond follow the same pattern with longer edges. Each step adds its computed sum to a set of candidates. After all centers and sizes are processed, the top three distinct values are extracted.

Complexity analysis

Time: For each of the m * n cells, you try up to min(m, n) / 2 sizes. Each rhombus of size s has 4 * s border cells to visit. Summing over all sizes gives an inner cost proportional to min(m, n)^2, leading to the overall bound.

Space: The set of sums holds at most m * n * min(m, n) entries in the worst case, but since we only need the top three, you could optimize with a bounded sorted structure. The grid itself is input, so extra space is effectively constant if you cap the collection at three elements.

Building blocks

Rhombus and diamond traversal

The key reusable pattern here is walking the border of a diamond (axis-aligned rhombus) in a 2D grid. The four edges each have a simple coordinate rule. Starting from the top vertex (r - s, c) and moving to the right vertex (r, c + s), both the row and column change by 1 per step. The same logic applies to the other three edges with different sign combinations:

for i in range(s):
    top_right = grid[r - s + i][c + i]
    right_bottom = grid[r + i][c + s - i]
    bottom_left = grid[r + s - i][c - i]
    left_top = grid[r - i][c - s + i]

This traversal pattern applies whenever you need to process the perimeter of a diamond shape. Variations include filling the interior of a rhombus, computing prefix sums along diagonals for faster border sums, and handling rhombuses rotated 45 degrees.

Top-K tracking with a set

When a problem asks for the "biggest K distinct values," a set combined with sorting is the simplest approach:

sums = set()
sums.add(value)
result = sorted(sums, reverse=True)[:k]

For small K (like 3 in this problem), you can also maintain a min-heap of size K or just keep a sorted list of three elements. The set-based approach is clean and avoids edge cases around duplicates. This pattern appears in many problems that ask for top-K, K-th largest, or K distinct extremes.

Edge cases

• Single cell grid: A 1x1 grid has only one rhombus (size 0). Return that single value.
• All identical values: Every rhombus sum of size 0 equals the same value. Larger rhombuses will have sums that are multiples of that value. The result may have fewer than three distinct entries.
• Grid too small for any rhombus beyond size 0: A 1xN or Mx1 grid has no room for size-1 rhombuses. Only individual cell values are candidates.
• Fewer than three distinct sums: If only one or two distinct sums exist across all possible rhombuses, return just those. The problem guarantees at least one cell.
• Large grid with uniform rows: Border sums grow linearly with size. Make sure your loop bounds correctly compute max_size to avoid index-out-of-bounds errors.

From understanding to recall

You now understand the enumeration approach: pick every center, try every size, walk the four edges, and collect distinct sums. The rhombus traversal pattern with its four coordinate rules is the core building block. Under interview pressure, the tricky part is getting the loop indices right for each edge of the diamond. Which coordinate increments, which decrements, and how to avoid double-counting corners are details that slip away if you have not practiced them recently.

Spaced repetition locks in those details. You write the four-edge traversal loop from scratch, verify the index arithmetic against a small grid, and repeat it on an expanding schedule. After a few rounds, picking the right signs for each edge becomes automatic. You see "rhombus in a grid" and the traversal pattern flows out without hesitation.

Related posts

• Spiral Matrix - Another matrix traversal that follows a specific geometric pattern
• 01 Matrix - Matrix problem requiring careful enumeration of positions
• Cells with Odd Values in a Matrix - Another grid-based counting problem