Get Biggest Three Rhombus Sums in a Grid

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.

• 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.

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.

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;
    }
}