Skip to main content
Talentd

Get Biggest Three Rhombus Sums in a Grid - Solution & Explanation

MediumArrayMathSortingHeap (Priority Queue)31 min readAsked at: Amazon, Uber, Google +1
Practice this problem

Problem Statement

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

Approach Overview

Problem 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 1: Brute Force Approach

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

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Optimized Precomputation Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m*n), Space Complexity: O(m*n).

Try this approach in the editor →

Approach 3: Enumerate Diamond Center + Prefix Sum + Ordered Set

We can preprocess to get two prefix sum arrays s_1 and s_2, where s_1[i][j] represents the sum of the elements on the upper left diagonal ending at (i, j), and s_2[i][j] represents the sum of the elements on the upper right diagonal ending at (i, j).

Next, we enumerate each position (i, j), first add grid[i][j] to the ordered set ss, and then enumerate the length k of the diamond. The sum of the diamond with (i, j) as the center and a side length of k is:

$ \begin{aligned} &\quad s_1[i + k][j] - s_1[i][j - k] + s_1[i][j + k] - s_1[i - k][j] \ &+ s_2[i][j - k] - s_2[i - k][j] + s_2[i + k][j] - s_2[i][j + k] \ &- grid[i + k - 1][j - 1] + grid[i - k - 1][j - 1] \end{aligned}

We add this value to the ordered set ss, while ensuring that the size of the ordered set ss does not exceed 3. Finally, we output the elements in the ordered set ss in reverse order.

The time complexity is O(m times n times min(m, n)), and the space complexity is O(m times n). Here, m and n$ are the number of rows and columns of the matrix, respectively.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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).

Enumerate Diamond Center + Prefix Sum + Ordered Set—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Rhombus EnumerationO(m * n * k)O(1)Good for understanding rhombus geometry and quick implementation when grid size is small
Diagonal Prefix Sum PrecomputationO(m * n * k)O(m * n)Preferred solution for large grids where repeated edge traversal becomes expensive

Video Solution

LeetCode 1878. Get Biggest Three Rhombus Sums in a Grid • Happy Coding • 5,373 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Get Biggest Three Rhombus Sums in a Grid easy or hard?
The problem is rated Medium on LeetCode. The main difficulty is correctly computing rhombus borders and avoiding double counting of corner cells. Using diagonal prefix sums simplifies the implementation and improves performance.
Get Biggest Three Rhombus Sums in a Grid Python/Java solution
Implementations typically iterate through grid cells, expand rhombus sizes, and compute border sums. Python, Java, C++, and JavaScript solutions often combine diagonal prefix sums with a TreeSet or heap to store the top three distinct results efficiently.
How to solve Get Biggest Three Rhombus Sums in a Grid in O(n)?
An O(n) solution is not feasible because the algorithm must examine rhombuses across the entire grid. The practical optimization is reducing edge traversal using diagonal prefix sums, which keeps the complexity around O(m * n * k) while making each border calculation constant time.
What is the best approach for Get Biggest Three Rhombus Sums in a Grid?
The most efficient approach precomputes diagonal prefix sums for both diagonal directions. This allows each rhombus border edge to be calculated in constant time instead of iterating through cells. After computing sums for all valid rhombuses, maintain the three largest distinct values using a set or small heap.
Is Get Biggest Three Rhombus Sums in a Grid asked at Google/Amazon/Meta?
Grid geometry and prefix-sum problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving matrix traversal, diagonal prefix sums, and shape-based region sums are common interview patterns.
What data structure is used in Get Biggest Three Rhombus Sums in a Grid?
The solution mainly uses arrays for the grid and for diagonal prefix sums. A small set or min-heap (priority queue) is used to keep track of the top three distinct rhombus sums while iterating through candidates.
What is the time complexity of Get Biggest Three Rhombus Sums in a Grid?
The typical optimized solution runs in O(m * n * k) time, where m and n are grid dimensions and k is the maximum rhombus radius (bounded by min(m, n)). Diagonal prefix sum preprocessing takes O(m * n) time and space.

Ready to solve this problem?

Practice Get Biggest Three Rhombus Sums in a Grid with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Fertile Pyramids in a Land