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] <= 105This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m*n), Space Complexity: O(m*n).
| 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). |
8 patterns to solve 80% Leetcode problems • Sahil & Sarra • 656,630 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