You are given an m x n integer matrix grid.
A rhombus sum is the sum of the elements that form the border of a regular rhombus shape in grid. The rhombus must have the shape of a square rotated 45 degrees with each of the corners centered in a grid cell. Below is an image of four valid rhombus shapes with the corresponding colored cells that should be included in each rhombus sum:
Note that the rhombus can have an area of 0, which is depicted by the purple rhombus in the bottom right corner.
Return the biggest three distinct rhombus sums in the grid in descending order. If there are less than three distinct values, return all of them.
Example 1:
Input: 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]] Output: [228,216,211] Explanation: The rhombus shapes for the three biggest distinct rhombus sums are depicted above. - Blue: 20 + 3 + 200 + 5 = 228 - Red: 200 + 2 + 10 + 4 = 216 - Green: 5 + 200 + 4 + 2 = 211
Example 2:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]] Output: [20,9,8] Explanation: The rhombus shapes for the three biggest distinct rhombus sums are depicted above. - Blue: 4 + 2 + 6 + 8 = 20 - Red: 9 (area 0 rhombus in the bottom right corner) - Green: 8 (area 0 rhombus in the bottom middle)
Example 3:
Input: grid = [[7,7,7]] Output: [7] Explanation: All three possible rhombus sums are the same, so return [7].
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 501 <= grid[i][j] <= 105Problem Overview: You are given an m x n grid of integers. A rhombus is formed by choosing a center and expanding diagonally to create a diamond shape. The task is to compute the border sum of every possible rhombus in the grid and return the three largest distinct sums. Single cells count as rhombuses of size 0.
Approach 1: Brute Force Rhombus Enumeration (Time: O(m * n * k), Space: O(1))
Iterate over every cell and treat it as the top vertex of a rhombus. For each position, expand the rhombus size while staying inside grid boundaries. Each expansion adds four edges: down-left, down-right, up-left, and up-right. Traverse these edges and accumulate the border sum manually. Maintain a small structure (like a set or min-heap of size three) to keep the largest distinct sums seen so far. This approach directly simulates rhombus borders and works well for moderate grid sizes. It relies heavily on careful boundary checks and repeated traversal of edges in the matrix.
Approach 2: Diagonal Prefix Sum Precomputation (Time: O(m * n * k), Space: O(m * n))
The optimized method avoids repeatedly walking along rhombus edges. Precompute two diagonal prefix sum arrays: one for the top-left to bottom-right direction and another for the top-right to bottom-left direction. With these prefix sums, the sum of any diagonal segment can be calculated in O(1). For each possible rhombus center and size, compute the four border edges using constant-time diagonal range queries instead of iterating through cells. Combine the four edge sums and subtract overlapping corners to avoid double counting. Track the largest three distinct values using a small heap or ordered set. This approach reduces repeated work and is significantly faster when many rhombuses are evaluated. It leverages techniques from prefix sum and efficient array preprocessing.
Recommended for interviews: Start by explaining the brute force enumeration to demonstrate understanding of rhombus geometry and boundary handling. Interviewers typically expect the optimized version that precomputes diagonal prefix sums. The optimized approach shows stronger algorithmic thinking because you transform repeated edge traversal into constant-time range queries.
This approach explores every possible rhombus of various sizes centered around each grid cell. We calculate the rhombus sum by considering the border cells for each possible size and then maintain a set of the unique sums to retrieve the largest three.
This solution calculates the rhombus sums for each potential rhombus in the grid. For each center, we compute the sums of rhombi formed by extending outwards symmetrically. Each sum is then stored uniquely, and finally, the largest three rhombus sums are output.
The time complexity is approximately O(m*n*k) where k is constrained by the smallest dimension of the grid. Space complexity is O(m*n) to store unique sums.
Instead of recalculating rhombus sums anew each time, this method precomputes partial sums as prefix sums. This reduces repeated computation and enhances overall efficiency.
This solution uses precomputed auxiliary data (like prefix sums) to construct rhombus sums without redundant calculations, ensuring every grid cell is considered for every size efficiently.
Time Complexity: O(m*n), Space Complexity: O(m*n).
We can preprocess to get two prefix sum arrays s_1 and s_2, where s_1[i][j] represents the sum of the elements on the upper left diagonal ending at (i, j), and s_2[i][j] represents the sum of the elements on the upper right diagonal ending at (i, j).
Next, we enumerate each position (i, j), first add grid[i][j] to the ordered set ss, and then enumerate the length k of the diamond. The sum of the diamond with (i, j) as the center and a side length of k is:
$
\begin{aligned}
&\quad s_1[i + k][j] - s_1[i][j - k] + s_1[i][j + k] - s_1[i - k][j] \
&+ s_2[i][j - k] - s_2[i - k][j] + s_2[i + k][j] - s_2[i][j + k] \
&- grid[i + k - 1][j - 1] + grid[i - k - 1][j - 1]
\end{aligned}
We add this value to the ordered set ss, while ensuring that the size of the ordered set ss does not exceed 3. Finally, we output the elements in the ordered set ss in reverse order.
The time complexity is O(m times n times min(m, n)), and the space complexity is O(m times n). Here, m and n$ are the number of rows and columns of the matrix, respectively.
| Approach | Complexity |
|---|---|
| Brute Force Approach | The time complexity is approximately O(m*n*k) where k is constrained by the smallest dimension of the grid. Space complexity is O(m*n) to store unique sums. |
| Optimized Precomputation Approach | Time Complexity: O(m*n), Space Complexity: O(m*n). |
| Enumerate Diamond Center + Prefix Sum + Ordered Set | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Rhombus Enumeration | O(m * n * k) | O(1) | Good for understanding rhombus geometry and quick implementation when grid size is small |
| Diagonal Prefix Sum Precomputation | O(m * n * k) | O(m * n) | Preferred solution for large grids where repeated edge traversal becomes expensive |
Get Biggest Three Rhombus Sums in a Grid | Brute Force | Optimal | Leetcode 1878 | codestorywithMIK • codestorywithMIK • 8,553 views views
Watch 9 more video solutions →Practice Get Biggest Three Rhombus Sums in a Grid with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor