Watch 10 video solutions for Get Biggest Three Rhombus Sums in a Grid, a medium level problem involving Array, Math, Sorting. This walkthrough by codestorywithMIK has 8,553 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |