Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1878. Get Biggest Three Rhombus Sums in a Grid - Leetcode Solution

Code Implementation

class Solution:
    def getBiggestThree(self, grid):
        import heapq
        m, n = len(grid), len(grid[0])
        res = set()
        for i in range(m):
            for j in range(n):
                res.add(grid[i][j])
                max_len = min(i, m - 1 - i, j, n - 1 - j)
                for l in range(1, max_len + 1):
                    s = 0
                    x, y = i - l, j
                    for k in range(l):
                        s += grid[x + k][y + k]
                    x, y = i, j + l
                    for k in range(l):
                        s += grid[x + k][y - k]
                    x, y = i + l, j
                    for k in range(l):
                        s += grid[x - k][y - k]
                    x, y = i, j - l
                    for k in range(l):
                        s += grid[x - k][y + k]
                    s -= grid[i - l][j]
                    s -= grid[i][j + l]
                    s -= grid[i + l][j]
                    s -= grid[i][j - l]
                    res.add(s)
        return sorted(res, reverse=True)[:3]
      
class Solution {
public:
    vector<int> getBiggestThree(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        set<int> res;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                res.insert(grid[i][j]);
                int max_len = min({i, m - 1 - i, j, n - 1 - j});
                for (int l = 1; l <= max_len; ++l) {
                    int s = 0;
                    int x = i - l, y = j;
                    for (int k = 0; k < l; ++k)
                        s += grid[x + k][y + k];
                    x = i, y = j + l;
                    for (int k = 0; k < l; ++k)
                        s += grid[x + k][y - k];
                    x = i + l, y = j;
                    for (int k = 0; k < l; ++k)
                        s += grid[x - k][y - k];
                    x = i, y = j - l;
                    for (int k = 0; k < l; ++k)
                        s += grid[x - k][y + k];
                    s -= grid[i - l][j];
                    s -= grid[i][j + l];
                    s -= grid[i + l][j];
                    s -= grid[i][j - l];
                    res.insert(s);
                }
            }
        }
        vector<int> ans;
        for (auto it = res.rbegin(); it != res.rend() && ans.size() < 3; ++it)
            ans.push_back(*it);
        return ans;
    }
};
      
class Solution {
    public int[] getBiggestThree(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        TreeSet<Integer> res = new TreeSet<>();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                res.add(grid[i][j]);
                int max_len = Math.min(Math.min(i, m - 1 - i), Math.min(j, n - 1 - j));
                for (int l = 1; l <= max_len; ++l) {
                    int s = 0;
                    int x = i - l, y = j;
                    for (int k = 0; k < l; ++k)
                        s += grid[x + k][y + k];
                    x = i; y = j + l;
                    for (int k = 0; k < l; ++k)
                        s += grid[x + k][y - k];
                    x = i + l; y = j;
                    for (int k = 0; k < l; ++k)
                        s += grid[x - k][y - k];
                    x = i; y = j - l;
                    for (int k = 0; k < l; ++k)
                        s += grid[x - k][y + k];
                    s -= grid[i - l][j];
                    s -= grid[i][j + l];
                    s -= grid[i + l][j];
                    s -= grid[i][j - l];
                    res.add(s);
                }
            }
        }
        int[] ans = new int[Math.min(3, res.size())];
        int idx = 0;
        for (Integer v : res.descendingSet()) {
            if (idx == 3) break;
            ans[idx++] = v;
        }
        return ans;
    }
}
      
var getBiggestThree = function(grid) {
    const m = grid.length, n = grid[0].length;
    const res = new Set();
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            res.add(grid[i][j]);
            let max_len = Math.min(i, m - 1 - i, j, n - 1 - j);
            for (let l = 1; l <= max_len; ++l) {
                let s = 0;
                let x = i - l, y = j;
                for (let k = 0; k < l; ++k)
                    s += grid[x + k][y + k];
                x = i; y = j + l;
                for (let k = 0; k < l; ++k)
                    s += grid[x + k][y - k];
                x = i + l; y = j;
                for (let k = 0; k < l; ++k)
                    s += grid[x - k][y - k];
                x = i; y = j - l;
                for (let k = 0; k < l; ++k)
                    s += grid[x - k][y + k];
                s -= grid[i - l][j];
                s -= grid[i][j + l];
                s -= grid[i + l][j];
                s -= grid[i][j - l];
                res.add(s);
            }
        }
    }
    return Array.from(res).sort((a, b) => b - a).slice(0, 3);
};

Problem Description

Given a 2D integer grid, you are asked to find the three largest unique sums of rhombus-shaped areas in the grid. A rhombus is defined by a center cell and a "size" (the distance from the center to one of the corners), and its sum is the sum of the numbers on its border. The rhombus can be of size 0 (just a single cell), or larger, as long as it fits entirely within the grid. You must not count duplicate sums, and you must not reuse the same rhombus (even if they have the same sum). The function should return an array of the largest three unique rhombus sums in descending order. If there are less than three, return as many as possible.

Thought Process

At first glance, you might think of brute-forcing every possible rhombus in the grid, summing their borders, and keeping track of the largest sums. However, this could be slow, especially for larger grids, because there are many possible centers and sizes. To optimize, we need to:
  • Recognize that a rhombus border can be traced in four straight lines (top-right, bottom-right, bottom-left, top-left).
  • Notice that rhombuses of size zero are just single cells.
  • Avoid duplicate sums by using a set.
  • Only consider rhombuses that fit entirely within the grid, based on the center and size.
  • Efficiently collect and sort the unique sums to get the top three.
The challenge is to carefully calculate the rhombus border sums and avoid counting the same border cell multiple times.

Solution Approach

To solve this problem efficiently, we follow these steps:
  1. Iterate through every cell in the grid, treating each as a potential rhombus center.
  2. For each center, try all possible rhombus sizes that fit within the grid. The maximum size is limited by the distance to the grid's edges.
  3. For each valid rhombus, sum the values on its border. This involves moving in four diagonal directions from the center, each for 'size' steps.
  4. For size zero, the sum is just the center cell's value.
  5. For larger sizes, carefully add each border cell only once. Since the four corners are shared between two sides each, we must subtract the four corners once to avoid double-counting.
  6. Store each unique sum in a set to avoid duplicates.
  7. After collecting all possible unique sums, sort them in descending order and return the top three.
This approach ensures that we consider all possible rhombuses without unnecessary recomputation or duplicate counting.

Example Walkthrough

Suppose the input grid is:
  • 3 4 5 1
  • 2 7 6 3
  • 1 8 9 4
  • 2 3 4 5
Step by step:
  1. Start with cell (1,1) (value 7). The largest possible rhombus size is 1 (since size 2 would go out of bounds).
  2. For size 0: sum = 7.
  3. For size 1: the border is (0,1), (1,2), (2,1), (1,0): values 4, 6, 8, 2. Sum = 4 + 6 + 8 + 2 = 20.
  4. Repeat for every possible center and size, collecting all unique sums.
  5. After all iterations, suppose the unique sums are [20, 18, 16, 12, 11, 9, 8, 7, 6, 5, 4, 3, 2, 1].
  6. Return the top three: [20, 18, 16].
This example shows how each rhombus is traced, summed, and stored.

Time and Space Complexity

  • Brute-force approach: For each cell (O(mn)), try each possible rhombus size (O(min(m, n))), and for each, sum the border (O(size)). This leads to O(mn * min(m, n) * size), which can be expensive.
  • Optimized approach: We still check all centers and sizes, but only sum the border (not the full area), and use a set for unique sums. The time complexity is O(mn * min(m, n)), since each border sum is O(size) but size is bounded by min(m, n).
  • Space complexity: O(U), where U is the number of unique rhombus sums (at most mn * min(m, n)), but in practice much less. Extra space is used for the set and the result array.

Summary

The problem asks us to find the largest three unique rhombus border sums in a grid. By treating each cell as a center and considering all possible rhombus sizes, we can efficiently compute all border sums using careful diagonal traversal. Using a set to track unique sums and sorting for the top three ensures correctness. The solution is elegant because it leverages geometric patterns, set uniqueness, and efficient enumeration without redundant computation.