LeetCode 1878 – Get Biggest Three Rhombus Sums in a Grid

In this article we will solve LeetCode Problem 1878 – Get Biggest Three Rhombus Sums in a Grid. This is a very interesting grid + prefix sum problem that requires understanding how to traverse a rhombus shape inside a matrix efficiently.

📺 Video Explanation

🧩 Problem Summary

A rhombus is a diamond-shaped structure where we only consider the border cells. The interior elements are not included in the sum.

🔷 What Does a Rhombus Look Like?

      *
    *   *
  *       *
    *   *
      *

Example inside a grid:

      4
    3   4
  20     40
    5   5
      4

The sum includes only the border values.

🟦 Key Observations

• Every cell can be a rhombus of size 0.
• Larger rhombuses expand diagonally.
• We only sum the four edges of the rhombus.
• We must return the top 3 distinct sums.

⚡ Optimization Idea

We maintain two prefix arrays:

• sum1 → diagonal ↘
• sum2 → diagonal ↙

This allows us to compute rhombus borders in O(1) time.

💻 Java Solution

class Solution {

    public int[] getBiggestThree(int[][] grid) {

        int m = grid.length;
        int n = grid[0].length;

        TreeSet<Integer> set = new TreeSet<>();

        for(int r=0;r<m;r++){
            for(int c=0;c<n;c++){

                set.add(grid[r][c]);

                for(int k=1;r-k>=0 && r+k<m && c-k>=0 && c+k<n;k++){

                    int sum=0;

                    int row=r-k;
                    int col=c;

                    for(int i=0;i<k;i++)
                        sum+=grid[row+i][col+i];

                    for(int i=0;i<k;i++)
                        sum+=grid[row+k+i][col+k-i];

                    for(int i=0;i<k;i++)
                        sum+=grid[row+2*k-i][col-i];

                    for(int i=0;i<k;i++)
                        sum+=grid[row+k-i][col-k+i];

                    set.add(sum);
                }
            }
        }

        int size=Math.min(3,set.size());
        int[] res=new int[size];

        for(int i=size-1;i>=0;i--)
            res[i]=set.pollLast();

        return res;
    }
}

⏱ Complexity Analysis

Time Complexity

O(m * n * min(m,n))

Space Complexity

O(1)

🚀 Key Takeaways

• Rhombus traversal involves 4 diagonal edges.
• Diagonal prefix sums speed up calculations.
• Using a TreeSet helps maintain the top 3 unique sums.

📌 Final Thoughts

This problem is a great example of combining geometry inside grids with prefix sum optimization. Once you visualize the rhombus structure, the solution becomes much easier to implement.