# Get Biggest Three Rhombus Sums in a Grid
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/get-biggest-three-rhombus-sums-in-a-grid)
Canonical: https://scaleengineer.com/dsa/problems/get-biggest-three-rhombus-sums-in-a-grid
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue), Matrix
**Companies:** [Capital One](https://scaleengineer.com/companies/capital-one), [Quora](https://scaleengineer.com/companies/quora)
---
## Problem
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**:

![](https://assets.glich.co/dsa/get-biggest-three-rhombus-sums-in-a-grid/image0.png) 

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:**

![](https://assets.glich.co/dsa/get-biggest-three-rhombus-sums-in-a-grid/image1.png) 

**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:**

![](https://assets.glich.co/dsa/get-biggest-three-rhombus-sums-in-a-grid/image2.png) 

**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.length`
* `n == grid[i].length`
* `1 <= m, n <= 50`
* `1 <= grid[i][j] <= 105`

# Approaches
## Brute-Force Simulation
This approach directly simulates the process of finding every possible rhombus in the grid. We iterate through each cell as a potential center of a rhombus. For each center, we expand outwards to form rhombuses of increasing sizes, as long as they stay within the grid boundaries. For each valid rhombus, we calculate its sum by traversing its border and adding up the cell values.
**Time:** O(m * n * min(m, n)^2). We iterate through `m * n` possible centers. For each center, we iterate through possible rhombus sizes `k`, where the maximum `k` is `O(min(m, n))`. For each size `k`, calculating the sum takes `O(k)` time. For a square grid of size `N`, this is `O(N^4)`. · **Space:** O(m * n * min(m, n)). In the worst case, every rhombus could have a unique sum. The number of possible rhombuses is O(m * n * min(m, n)). The `TreeSet` would store all these sums.
**Pros:** Conceptually simple and follows the problem definition directly.; Relatively easy to implement without complex data structures.
**Cons:** Highly inefficient due to redundant calculations. The sum for each rhombus is computed from scratch.; May be too slow for larger grid sizes, although it passes for the given constraints (`m, n <= 50`).
### Explanation
We use a `TreeSet` to store the distinct rhombus sums. A `TreeSet` is useful because it automatically keeps the sums sorted and handles duplicates.

We iterate through every cell `(r, c)` of the grid. This cell will serve as the center of a potential rhombus.

For each center `(r, c)`, we first consider a rhombus of size 0. The sum is simply the value of the cell `grid[r][c]`. We add this to our set.

Then, we start a loop for the rhombus size `k`, starting from `k=1`. We expand the rhombus as long as its four corners `(r-k, c)`, `(r, c+k)`, `(r+k, c)`, and `(r, c-k)` are all within the grid's boundaries.

For each valid size `k`, we calculate the sum of the elements on its border. This is done by simulating a walk along the four sides of the rhombus, taking care not to double-count the corner elements.

The calculated sum is added to the `TreeSet`.

After checking all possible centers and sizes, the `TreeSet` contains all distinct rhombus sums in ascending order. We extract the top three largest sums (or fewer if there aren't that many) and return them in descending order.

```java
import java.util.*;

class Solution {
    public int[] getBiggestThree(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // Use a TreeSet to keep sums sorted and unique
        TreeSet<Integer> sums = new TreeSet<>();

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                // Size 0 rhombus
                sums.add(grid[r][c]);

                // Size k > 0 rhombuses
                for (int k = 1; ; k++) {
                    // Check if the rhombus is within bounds
                    if (r - k < 0 || r + k >= m || c - k < 0 || c + k >= n) {
                        break;
                    }

                    // Calculate sum for rhombus of size k
                    int currentSum = 0;
                    // Top to right (excluding right corner)
                    for (int i = 0; i < k; i++) {
                        currentSum += grid[r - k + i][c + i];
                    }
                    // Right to bottom (excluding bottom corner)
                    for (int i = 0; i < k; i++) {
                        currentSum += grid[r + i][c + k - i];
                    }
                    // Bottom to left (excluding left corner)
                    for (int i = 0; i < k; i++) {
                        currentSum += grid[r + k - i][c - i];
                    }
                    // Left to top (excluding top corner)
                    for (int i = 0; i < k; i++) {
                        currentSum += grid[r - i][c - k + i];
                    }
                    sums.add(currentSum);
                }
            }
        }

        // Extract the top 3 sums
        int count = Math.min(3, sums.size());
        int[] result = new int[count];
        for (int i = 0; i < count; i++) {
            result[i] = sums.pollLast();
        }
        return result;
    }
}
```
### Algorithm
*   Initialize a `TreeSet` called `sums` to store distinct rhombus sums in sorted order.
*   Iterate through each cell `(r, c)` from `(0, 0)` to `(m-1, n-1)` to use as a rhombus center.
*   For each center `(r, c)`:
    *   Add `grid[r][c]` to `sums` (this is a rhombus of size 0).
    *   Start a loop for rhombus size `k` from 1.
    *   Check if a rhombus of size `k` centered at `(r, c)` is fully contained within the grid. If not, break the loop for `k`.
    *   If it is contained, calculate the sum of its border elements by iterating along its four sides.
    *   Add the calculated sum to `sums`.
*   After all iterations, `sums` will contain all distinct rhombus sums.
*   Create a result array of size `min(3, sums.size())`.
*   Pop the largest elements from `sums` and fill the result array.
*   Return the result array.

## Dynamic Programming with Diagonal Prefix Sums
This approach optimizes the sum calculation by pre-computing prefix sums along the two diagonal directions. A rhombus's border is composed of four diagonal segments. By using pre-computed sums, we can find the sum of any diagonal segment in `O(1)` time. This reduces the time to calculate each rhombus sum from `O(k)` to `O(1)`, significantly improving the overall performance.
**Time:** O(m * n * min(m, n)). Pre-computation of prefix sums takes `O(m * n)`. Then we iterate through all `m * n` centers, and for each center, iterate through `O(min(m, n))` sizes. Each sum calculation is `O(1)`. For a square grid of size `N`, this is `O(N^3)`. · **Space:** O(m * n). We need `O(m * n)` space for the two prefix sum arrays `diag1` and `diag2`. The `TreeSet` also uses space, but the dominant factor for auxiliary space is the prefix sum arrays.
**Pros:** Much more efficient than the brute-force approach.; Reduces the complexity of the innermost loop from O(k) to O(1).
**Cons:** More complex to implement, especially the prefix sum calculation and the formula to get the rhombus sum.; Requires extra space for the prefix sum arrays.
### Explanation
The key insight is that the four sides of a rhombus lie on two main diagonals and two anti-diagonals. We can pre-calculate prefix sums for all such diagonals in the grid.

We create two auxiliary 2D arrays, `diag1` and `diag2`, of the same size as the grid.
*   `diag1[i][j]` will store the sum of elements on the main diagonal (top-left to bottom-right) ending at `(i, j)`. It's calculated as `diag1[i][j] = grid[i][j] + (i > 0 && j > 0 ? diag1[i-1][j-1] : 0)`.
*   `diag2[i][j]` will store the sum of elements on the anti-diagonal (top-right to bottom-left) ending at `(i, j)`. It's calculated as `diag2[i][j] = grid[i][j] + (i > 0 && j < n-1 ? diag2[i-1][j+1] : 0)`.

These two prefix sum arrays can be computed in `O(m * n)` time.

After pre-computation, we iterate through all possible rhombus centers `(r, c)` and sizes `k`. The sum for a rhombus of size `k > 0` can now be calculated in `O(1)` time using the prefix sum arrays. The sum is the total of four diagonal segments. A segment sum from point A to B on a diagonal can be calculated as `prefix[B] - prefix[A] + grid[A]`. Summing the four segments of the rhombus border and simplifying gives a constant time formula.

```java
import java.util.*;

class Solution {
    public int[] getBiggestThree(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // diag1: prefix sums for top-left to bottom-right diagonals
        int[][] diag1 = new int[m][n];
        // diag2: prefix sums for top-right to bottom-left diagonals
        int[][] diag2 = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                diag1[i][j] = grid[i][j] + (i > 0 && j > 0 ? diag1[i - 1][j - 1] : 0);
            }
            for (int j = n - 1; j >= 0; j--) {
                diag2[i][j] = grid[i][j] + (i > 0 && j < n - 1 ? diag2[i - 1][j + 1] : 0);
            }
        }

        TreeSet<Integer> sums = new TreeSet<>();
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                sums.add(grid[r][c]); // Size 0 rhombus
                
                // Iterate through possible rhombus sizes k > 0
                for (int k = 1; r - k >= 0 && r + k < m && c - k >= 0 && c + k < n; k++) {
                    // Corners
                    int topR = r - k, topC = c;
                    int rightR = r, rightC = c + k;
                    int bottomR = r + k, bottomC = c;
                    int leftR = r, leftC = c - k;

                    // Sum of segments: (T->R) + (R->B) + (B->L) + (L->T)
                    int sumTR = diag2[rightR][rightC] - diag2[topR][topC];
                    int sumRB = diag1[bottomR][bottomC] - diag1[rightR][rightC];
                    int sumBL = diag2[bottomR][bottomC] - diag2[leftR][leftC];
                    int sumLT = diag1[leftR][leftC] - diag1[topR][topC];
                    
                    // The above subtractions exclude the top and bottom corners.
                    // Add them back to get the full border sum.
                    int totalSum = sumTR + sumRB + sumBL + sumLT + grid[topR][topC] + grid[bottomR][bottomC];
                    sums.add(totalSum);
                }
            }
        }

        int count = Math.min(3, sums.size());
        int[] result = new int[count];
        for (int i = 0; i < count; i++) {
            result[i] = sums.pollLast();
        }
        return result;
    }
}
```
### Algorithm
*   Create two `m x n` prefix sum arrays, `diag1` and `diag2`.
*   Populate `diag1[i][j]` with the sum of elements on the main diagonal (top-left to bottom-right) ending at `(i, j)`.
*   Populate `diag2[i][j]` with the sum of elements on the anti-diagonal (top-right to bottom-left) ending at `(i, j)`.
*   Initialize a `TreeSet` called `sums`.
*   Iterate through each cell `(r, c)` as a potential rhombus center.
*   Add `grid[r][c]` to `sums` (for size 0 rhombus).
*   Loop for size `k` from 1, as long as the rhombus is in-bounds.
*   For each `k`, identify the four corners: `T(r-k, c)`, `R(r, c+k)`, `B(r+k, c)`, `L(r, c-k)`.
*   Calculate the sum of the border using the pre-computed `diag1` and `diag2` arrays in `O(1)` time.
*   Add the sum to the `TreeSet`.
*   After all iterations, extract the top 3 largest elements from the `TreeSet` and return them in descending order.

# Solutions
### Java

```java
class Solution {
public
  int[] getBiggestThree(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] s1 = new int[m + 1][n + 2];
    int[][] s2 = new int[m + 1][n + 2];
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        s1[i][j] = s1[i - 1][j - 1] + grid[i - 1][j - 1];
        s2[i][j] = s2[i - 1][j + 1] + grid[i - 1][j - 1];
      }
    }
    TreeSet<Integer> ss = new TreeSet<>();
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        int l = Math.min(Math.min(i - 1, m - i), Math.min(j - 1, n - j));
        ss.add(grid[i - 1][j - 1]);
        for (int k = 1; k <= l; ++k) {
          int a = s1[i + k][j] - s1[i][j - k];
          int b = s1[i][j + k] - s1[i - k][j];
          int c = s2[i][j - k] - s2[i - k][j];
          int d = s2[i + k][j] - s2[i][j + k];
          ss.add(a + b + c + d - grid[i + k - 1][j - 1] +
                 grid[i - k - 1][j - 1]);
        }
        while (ss.size() > 3) {
          ss.pollFirst();
        }
      }
    }
    int[] ans = new int[ss.size()];
    for (int i = 0; i < ans.length; ++i) {
      ans[i] = ss.pollLast();
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> getBiggestThree(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> s1(m + 1, vector<int>(n + 2));
    vector<vector<int>> s2(m + 1, vector<int>(n + 2));
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        s1[i][j] = s1[i - 1][j - 1] + grid[i - 1][j - 1];
        s2[i][j] = s2[i - 1][j + 1] + grid[i - 1][j - 1];
      }
    }
    set<int> ss;
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        int l = min({i - 1, m - i, j - 1, n - j});
        ss.insert(grid[i - 1][j - 1]);
        for (int k = 1; k <= l; ++k) {
          int a = s1[i + k][j] - s1[i][j - k];
          int b = s1[i][j + k] - s1[i - k][j];
          int c = s2[i][j - k] - s2[i - k][j];
          int d = s2[i + k][j] - s2[i][j + k];
          ss.insert(a + b + c + d - grid[i + k - 1][j - 1] +
                    grid[i - k - 1][j - 1]);
        }
        while (ss.size() > 3) {
          ss.erase(ss.begin());
        }
      }
    }
    return vector<int>(ss.rbegin(), ss.rend());
  }
};

```

### Python

```python
from sortedcontainers import SortedSet class Solution : def getBiggestThree ( self , grid : List [ List [ int ]]) -> List [ int ]: m , n = len ( grid ), len ( grid [ 0 ]) s1 = [[ 0 ] * ( n + 2 ) for _ in range ( m + 1 )] s2 = [[ 0 ] * ( n + 2 ) for _ in range ( m + 1 )] for i , row in enumerate ( grid , 1 ): for j , x in enumerate ( row , 1 ): s1 [ i ][ j ] = s1 [ i - 1 ][ j - 1 ] + x s2 [ i ][ j ] = s2 [ i - 1 ][ j + 1 ] + x ss = SortedSet () for i , row in enumerate ( grid , 1 ): for j , x in enumerate ( row , 1 ): l = min ( i - 1 , m - i , j - 1 , n - j ) ss . add ( x ) for k in range ( 1 , l + 1 ): a = s1 [ i + k ][ j ] - s1 [ i ][ j - k ] b = s1 [ i ][ j + k ] - s1 [ i - k ][ j ] c = s2 [ i ][ j - k ] - s2 [ i - k ][ j ] d = s2 [ i + k ][ j ] - s2 [ i ][ j + k ] ss . add ( a + b + c + d - grid [ i + k - 1 ][ j - 1 ] + grid [ i - k - 1 ][ j - 1 ] ) while len ( ss ) > 3 : ss . remove ( ss [ 0 ]) return list ( ss )[:: - 1 ]
```