Get Biggest Three Rhombus Sums in a Grid

Med

#1714Time: 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.2 companies

Patterns

Math Prefix Sum

Algorithms

Sorting

Data structures

Array Heap (Priority Queue)Matrix

Companies

Capital One Quora

Prompt

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] <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1import java.util.*;2 3class Solution {4    public int[] getBiggestThree(int[][] grid) {5        int m = grid.length;6        int n = grid[0].length;7        // Use a TreeSet to keep sums sorted and unique8        TreeSet<Integer> sums = new TreeSet<>();9 10        for (int r = 0; r < m; r++) {11            for (int c = 0; c < n; c++) {12                // Size 0 rhombus13                sums.add(grid[r][c]);14 15                // Size k > 0 rhombuses16                for (int k = 1; ; k++) {17                    // Check if the rhombus is within bounds18                    if (r - k < 0 || r + k >= m || c - k < 0 || c + k >= n) {19                        break;20                    }21 22                    // Calculate sum for rhombus of size k23                    int currentSum = 0;24                    // Top to right (excluding right corner)25                    for (int i = 0; i < k; i++) {26                        currentSum += grid[r - k + i][c + i];27                    }28                    // Right to bottom (excluding bottom corner)29                    for (int i = 0; i < k; i++) {30                        currentSum += grid[r + i][c + k - i];31                    }32                    // Bottom to left (excluding left corner)33                    for (int i = 0; i < k; i++) {34                        currentSum += grid[r + k - i][c - i];35                    }36                    // Left to top (excluding top corner)37                    for (int i = 0; i < k; i++) {38                        currentSum += grid[r - i][c - k + i];39                    }40                    sums.add(currentSum);41                }42            }43        }44 45        // Extract the top 3 sums46        int count = Math.min(3, sums.size());47        int[] result = new int[count];48        for (int i = 0; i < count; i++) {49            result[i] = sums.pollLast();50        }51        return result;52    }53}

Complexity

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.

Trade-offs

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

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.

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.

Walkthrough

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.

1import java.util.*;2 3class Solution {4    public int[] getBiggestThree(int[][] grid) {5        int m = grid.length;6        int n = grid[0].length;7 8        // diag1: prefix sums for top-left to bottom-right diagonals9        int[][] diag1 = new int[m][n];10        // diag2: prefix sums for top-right to bottom-left diagonals11        int[][] diag2 = new int[m][n];12 13        for (int i = 0; i < m; i++) {14            for (int j = 0; j < n; j++) {15                diag1[i][j] = grid[i][j] + (i > 0 && j > 0 ? diag1[i - 1][j - 1] : 0);16            }17            for (int j = n - 1; j >= 0; j--) {18                diag2[i][j] = grid[i][j] + (i > 0 && j < n - 1 ? diag2[i - 1][j + 1] : 0);19            }20        }21 22        TreeSet<Integer> sums = new TreeSet<>();23        for (int r = 0; r < m; r++) {24            for (int c = 0; c < n; c++) {25                sums.add(grid[r][c]); // Size 0 rhombus26                27                // Iterate through possible rhombus sizes k > 028                for (int k = 1; r - k >= 0 && r + k < m && c - k >= 0 && c + k < n; k++) {29                    // Corners30                    int topR = r - k, topC = c;31                    int rightR = r, rightC = c + k;32                    int bottomR = r + k, bottomC = c;33                    int leftR = r, leftC = c - k;34 35                    // Sum of segments: (T->R) + (R->B) + (B->L) + (L->T)36                    int sumTR = diag2[rightR][rightC] - diag2[topR][topC];37                    int sumRB = diag1[bottomR][bottomC] - diag1[rightR][rightC];38                    int sumBL = diag2[bottomR][bottomC] - diag2[leftR][leftC];39                    int sumLT = diag1[leftR][leftC] - diag1[topR][topC];40                    41                    // The above subtractions exclude the top and bottom corners.42                    // Add them back to get the full border sum.43                    int totalSum = sumTR + sumRB + sumBL + sumLT + grid[topR][topC] + grid[bottomR][bottomC];44                    sums.add(totalSum);45                }46            }47        }48 49        int count = Math.min(3, sums.size());50        int[] result = new int[count];51        for (int i = 0; i < count; i++) {52            result[i] = sums.pollLast();53        }54        return result;55    }56}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int[] getBiggestThree(int[][] grid) {4    int m = grid.length, n = grid[0].length;5    int[][] s1 = new int[m + 1][n + 2];6    int[][] s2 = new int[m + 1][n + 2];7    for (int i = 1; i <= m; ++i) {8      for (int j = 1; j <= n; ++j) {9        s1[i][j] = s1[i - 1][j - 1] + grid[i - 1][j - 1];10        s2[i][j] = s2[i - 1][j + 1] + grid[i - 1][j - 1];11      }12    }13    TreeSet<Integer> ss = new TreeSet<>();14    for (int i = 1; i <= m; ++i) {15      for (int j = 1; j <= n; ++j) {16        int l = Math.min(Math.min(i - 1, m - i), Math.min(j - 1, n - j));17        ss.add(grid[i - 1][j - 1]);18        for (int k = 1; k <= l; ++k) {19          int a = s1[i + k][j] - s1[i][j - k];20          int b = s1[i][j + k] - s1[i - k][j];21          int c = s2[i][j - k] - s2[i - k][j];22          int d = s2[i + k][j] - s2[i][j + k];23          ss.add(a + b + c + d - grid[i + k - 1][j - 1] +24                 grid[i - k - 1][j - 1]);25        }26        while (ss.size() > 3) {27          ss.pollFirst();28        }29      }30    }31    int[] ans = new int[ss.size()];32    for (int i = 0; i < ans.length; ++i) {33      ans[i] = ss.pollLast();34    }35    return ans;36  }37}

1class Solution {2public:3  vector<int> getBiggestThree(vector<vector<int>> &grid) {4    int m = grid.size(), n = grid[0].size();5    vector<vector<int>> s1(m + 1, vector<int>(n + 2));6    vector<vector<int>> s2(m + 1, vector<int>(n + 2));7    for (int i = 1; i <= m; ++i) {8      for (int j = 1; j <= n; ++j) {9        s1[i][j] = s1[i - 1][j - 1] + grid[i - 1][j - 1];10        s2[i][j] = s2[i - 1][j + 1] + grid[i - 1][j - 1];11      }12    }13    set<int> ss;14    for (int i = 1; i <= m; ++i) {15      for (int j = 1; j <= n; ++j) {16        int l = min({i - 1, m - i, j - 1, n - j});17        ss.insert(grid[i - 1][j - 1]);18        for (int k = 1; k <= l; ++k) {19          int a = s1[i + k][j] - s1[i][j - k];20          int b = s1[i][j + k] - s1[i - k][j];21          int c = s2[i][j - k] - s2[i - k][j];22          int d = s2[i + k][j] - s2[i][j + k];23          ss.insert(a + b + c + d - grid[i + k - 1][j - 1] +24                    grid[i - k - 1][j - 1]);25        }26        while (ss.size() > 3) {27          ss.erase(ss.begin());28        }29      }30    }31    return vector<int>(ss.rbegin(), ss.rend());32  }33};

1from 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 ]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem