LeetCode 1878 - Get Biggest Three Rhombus Sums in a Grid

Difficulty: 🟡 Medium
Topics: Array, Math, Sorting, Heap (Priority Queue), Matrix, Prefix Sum

Solution

Problem Understanding

The problem asks us to compute the largest three distinct rhombus sums in a given m x n integer grid. A rhombus in this context is a square rotated 45 degrees, whose corners align with grid cells. The rhombus sum includes only the border cells of this shape, not the interior. The rhombus can have a "size" of 0, meaning it consists of a single cell, which is valid.

The input is a 2D list of integers, grid, where grid[i][j] represents the value at row i and column j. The output is a list of up to three integers representing the largest distinct rhombus sums, in descending order.

Constraints indicate that the grid size is moderate (1 <= m, n <= 50) and each cell value is positive (1 <= grid[i][j] <= 10^5). This makes brute-force enumeration feasible for small rhombus sizes, but we need an efficient approach to handle the larger rhombus shapes near the grid boundaries. Edge cases include grids that are too small for large rhombi, grids where all values are identical, and grids with only one row or one column.

Approaches

Brute Force Approach:

The naive approach is to consider every possible center cell (i, j) and every possible rhombus size that fits within the grid bounds. For each rhombus, we manually sum the border cells by walking along the four edges. We would then maintain a set of rhombus sums to ensure distinct values. This approach works correctly but is inefficient because the number of rhombi grows roughly as O(m * n * min(m, n)), and summing each rhombus border requires O(size) operations. For a 50x50 grid, this can become expensive.

Optimal Approach:

We can optimize by noting that the rhombus border can be summed in four linear segments (top-right, top-left, bottom-left, bottom-right). We iterate through all valid centers (i, j) and all sizes that fit. For each rhombus, we compute the sum by walking along these four edges directly, which reduces redundant computation. A set keeps track of distinct sums, and we finally extract the top three sums by sorting in descending order. This method leverages the small grid size and direct computation for efficiency.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m * n * min(m, n)^2)	O(m * n)	Enumerate all rhombus centers and sizes, sum each border manually
Optimal	O(m * n * min(m, n))	O(m * n)	Sum rhombus borders using linear traversal along four edges, store in a set, extract top three

Algorithm Walkthrough

Initialize an empty set sums to store distinct rhombus sums.
Loop over each cell (i, j) in the grid. Treat this cell as the center of potential rhombi.
Add the single-cell rhombus sum (grid[i][j]) to the set.
Determine the maximum possible rhombus size from this center without exceeding grid boundaries.
For each valid size k > 0, compute the rhombus border sum by iterating along four edges: top-right, top-left, bottom-left, bottom-right.
Add the computed rhombus sum to the set of distinct sums.
After processing all cells and sizes, convert the set to a list, sort it in descending order, and return the top three values.

Why it works:

The algorithm systematically enumerates all possible rhombi without redundancy. By summing only the border, it respects the problem's definition. Using a set ensures distinct sums, and sorting guarantees descending order. The algorithm covers all valid rhombus sizes, including the single-cell (size 0) case.

Python Solution

from typing import List

class Solution:
    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:
        m, n = len(grid), len(grid[0])
        sums = set()
        
        for i in range(m):
            for j in range(n):
                # Single cell rhombus
                sums.add(grid[i][j])
                
                # Maximum possible rhombus size
                max_k = min(i, m-1-i, j, n-1-j)
                
                for k in range(1, max_k+1):
                    rhombus_sum = 0
                    # Top-right edge
                    for t in range(k):
                        rhombus_sum += grid[i-t][j+t]
                    # Bottom-right edge
                    for t in range(k):
                        rhombus_sum += grid[i-t+k][j+t+k]
                    # Bottom-left edge
                    for t in range(k):
                        rhombus_sum += grid[i+k-t][j+k+t]
                    # Top-left edge
                    for t in range(k):
                        rhombus_sum += grid[i+k-t][j-t]
                    
                    # Remove double-counted corners
                    rhombus_sum -= grid[i][j]
                    rhombus_sum -= grid[i-k][j+k]
                    rhombus_sum -= grid[i+k][j+k]
                    rhombus_sum -= grid[i+k][j-k]
                    
                    sums.add(rhombus_sum)
        
        return sorted(sums, reverse=True)[:3]

Implementation Notes:

The code starts by adding all single-cell rhombus sums. For each size k, it walks along the four edges, summing the values. Corners are visited twice in edge summing, so they are subtracted once to correct the total. Finally, a set ensures distinct sums, and sorting gives the descending order needed.

Go Solution

func getBiggestThree(grid [][]int) []int {
    m, n := len(grid), len(grid[0])
    sums := map[int]struct{}{}
    
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            sums[grid[i][j]] = struct{}{}
            maxK := min(min(i, m-1-i), min(j, n-1-j))
            for k := 1; k <= maxK; k++ {
                rhombusSum := 0
                for t := 0; t < k; t++ {
                    rhombusSum += grid[i-t][j+t]
                }
                for t := 0; t < k; t++ {
                    rhombusSum += grid[i-t+k][j+t+k]
                }
                for t := 0; t < k; t++ {
                    rhombusSum += grid[i+k-t][j+k+t]
                }
                for t := 0; t < k; t++ {
                    rhombusSum += grid[i+k-t][j-t]
                }
                // Remove double-counted corners
                rhombusSum -= grid[i][j]
                rhombusSum -= grid[i-k][j+k]
                rhombusSum -= grid[i+k][j+k]
                rhombusSum -= grid[i+k][j-k]
                
                sums[rhombusSum] = struct{}{}
            }
        }
    }
    
    distinct := []int{}
    for val := range sums {
        distinct = append(distinct, val)
    }
    sort.Sort(sort.Reverse(sort.IntSlice(distinct)))
    if len(distinct) > 3 {
        return distinct[:3]
    }
    return distinct
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Go-specific Notes:

Go uses a map as a set, and slices for the sorted list. The algorithm logic mirrors the Python version. Care is taken to avoid index out-of-bounds by computing maxK. Corners are corrected by subtracting double-counted values.

Worked Examples

Example 1:

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]]

Single-cell rhombus sums include values like 3, 4, 5, 200, etc.
Size-1 rhombus at center (2,2) sums the border: 20 + 3 + 200 + 5 = 228.
Other rhombi produce sums 216, 211, etc.
Distinct sums are collected in a set: {3,4,5,200,...,228,216,211}.
Sorted descending: [228,216,211,...].
Top 3 extracted: [228,216,211].

Example 2:

grid = [[1,2,3],
        [4,5,6],
        [7,8,9]]

Single-cell sums: 1-9
Size-1 rhombus: 4+2+6+8 = 20
Distinct sums: {1-9,20}
Sorted descending: [20,9,8]
Top 3: [20,9,8]

Example 3:

grid = [[7,7,7]]

Only single-cell