Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A rhombus is fixed by its bottom vertex and side length. Enumerating these choices covers every border, including the zero-size rhombus consisting of one cell. Since the answer asks for distinct sums, different rhombi with the same sum should be merged.

Approach

At each bottom vertex, insert its cell value. Increase the side length while the top, left, and right vertices remain in bounds. Add the four corners once, then the interior points along each of the four diagonal edges, excluding endpoints to avoid duplicate corners. Insert each border sum into a set. Finally sort the distinct sums in descending order and return the first three, or all of them if fewer exist. Interior cells are not included.

class Solution:
    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:
        n = len(grid)
        m = len(grid[0])
        res = set()

        for i in range(n):
            for j in range(m):
                res.add(grid[i][j])
                s = 1
                while i - s * 2 >= 0 and j - s >= 0 and j + s < m:
                    acc = (
                        grid[i][j] # bot
                        + grid[i - s * 2][j] # top
                        + grid[i - s][j - s] # left
                        + grid[i - s][j + s] # right
                    )
                    for step in range(1, s):
                        acc += (
                            grid[i - step][j - step] # bl
                            + grid[i - step][j + step] # br
                            + grid[i - s * 2 + step][j - step] # tl
                            + grid[i - s * 2 + step][j + step] # tr
                        )
                    res.add(acc)
                    s += 1

        res = list(res)
        res.sort(reverse = True)

        return res[:3]

Complexity analysis

Let r and c be the grid dimensions, d = min(r, c), and S the number of distinct rhombus sums produced. Time: O(r * c * d^2 + S log S) for border enumeration and final sorting. Auxiliary space: O(S).