1878. Get Biggest Three Rhombus Sums in a Grid


Problem Explanation

You are given an m x n integer matrix called grid. The goal of this problem is to find the three greatest rhombus sums in the 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.

For example, given the following grid:

1
2
31 1 1
41 2 1
51 1 1

The three greatest rhombus sums would be [2, 6, 8]. These rhombus sums correspond to the single cells (1,1), (0,0) and beside it, and (1,1) surrounding the whole grid.

Solution Approach

The main idea of the solution is to iterate through each cell of the grid and consider it as a potential top corner of a rhombus. Then, for each such cell, we check what the maximum size of a rhombus can be with its top corner at this cell, and then calculate the rhombus sum for each of its possible sizes. We store these sums in a set data structure, which is sorted by default, and only keep the top three greatest sums found so far. Finally, we return these three greatest sums in a reversed order as a vector.

Let's go step by step through the provided solution, with a small example grid:

1
2
3grid = [
4  [1, 1, 1],
5  [1, 2, 1],
6  [1, 1, 1]
7]
  1. Initialize a variable sums to store the top three rhombus sums found so far. We use a set data structure since it stores sorted elements by default.

  2. Iterate through each cell (i, j) of the grid.

  3. For each cell (i, j), check what the maximum size of a rhombus can be with its top corner at this cell. This is determined by the condition i + sz < m && i - sz >= 0 && j + 2 * sz < n. For each rhombus size sz, calculate the rhombus sum using the getSum() function.

  4. As we calculate a rhombus sum, insert it into the sums set. To maintain the top three sums, remove the smallest element in the set if its size gets larger than 3.

  5. Return the sums in the sums set, reversed, as a vector.

Let's see how this works for our example grid:

  1. Initialize sums to an empty set.

  2. Start iterating through the grid cells:

    • For cell (0, 0), the rhombus of size 0 has a sum of 1. Insert this into sums (sums = {1}).
    • For cell (0, 1), the rhombus of size 0 has a sum of 1. INSERT this into sums, do not insert since 1 is already present.
    • For cell (0, 2), the rhombus of size 0 has a sum of 1. INSERT this into sums, do not insert since 1 is already present.
    • For cell (1, 0), the rhombus of size 0 and 1 have sums of 1 and 6. Insert these sums into sums (sums = {1, 6}).
    • For cell (1, 1), the rhombus of size 0, 1, and 2 have sums of 2, 6, and 8. Insert these sums into sums (sums = {2, 6, 8}).
    • For cell (1, 2), the rhombus of size 0 and 1 have sums of 1 and 6. These sums are already in sums, so no changes.
    • For cell (2, 0), the rhombus of size 0 has a sum of 1. This sum is already in sums, so no changes.
    • For cell (2, 1), the rhombus of size 0 has a sum of 1. This sum is already in sums, so no changes.
    • For cell (2, 2), the rhombus of size 0 has a sum of 1. This sum is already in sums, so no changes.
  3. Return the elements in sums as a reversed vector: [2, 6, 8].

C++ Solution

1
2cpp
3class Solution {
4 public:
5  vector<int> getBiggestThree(vector<vector<int>>& grid) {
6    const int m = grid.size();
7    const int n = grid[0].size();
8    set<int> sums;
9
10    for (int i = 0; i < m; ++i)
11      for (int j = 0; j < n; ++j)
12        for (int sz = 0; i + sz < m && i - sz >= 0 && j + 2 * sz < n; ++sz) {
13          const int sum = sz == 0 ? grid[i][j] : getSum(grid, i, j, sz);
14          sums.insert(sum);
15          if (sums.size() > 3)
16            sums.erase(begin(sums));
17        }
18
19    return vector<int>(rbegin(sums), rend(sums));
20  }
21
22 private:
23  // Returns rhombus sum of grid with top grid (i, j) and edge size `sz`.
24  int getSum(const vector<vector<int>>& grid, int i, int j, int sz) {
25    int x = i;
26    int y = j;
27    int sum = 0;
28
29    // Go left down.
30    for (int k = 0; k < sz; ++k)
31      sum += grid[--x][++y];
32
33    // Go right down.
34    for (int k = 0; k < sz; ++k)
35      sum += grid[++x][++y];
36
37    // Go right up.
38    for (int k = 0; k < sz; ++k)
39      sum += grid[++x][--y];
40
41    // Go left up.
42    for (int k = 0; k < sz; ++k)
43      sum += grid[--x][--y];
44
45    return sum;
46  }
47};

Please note: Solutions in Python, Java, JavaScript, and C# are not provided as the main solution is in C++ and the description requested only one language solution.## Python Solution

1
2python
3class Solution(object):
4    def getBiggestThree(self, grid):
5        m, n = len(grid), len(grid[0])
6        sums = set()
7
8        for i in range(m):
9            for j in range(n):
10                for sz in range(m):
11                    if i + sz < m and i - sz >= 0 and j + 2 * sz < n:
12                        sum = 0 if sz == 0 else self.getSum(grid, i, j, sz)
13                        sums.add(sum)
14                        if len(sums) > 3:
15                            sums.remove(min(sums))
16
17        return sorted(sums, reverse=True)
18
19    # Returns rhombus sum of grid with top grid (i, j) and edge size `sz`.
20    def getSum(self, grid, i, j, sz):
21        x, y = i, j
22        sum = 0
23
24        # Go left down.
25        for k in range(sz):
26            x -= 1
27            y += 1
28            sum += grid[x][y]
29
30        # Go right down.
31        for k in range(sz):
32            x += 1
33            y += 1
34            sum += grid[x][y]
35
36        # Go right up.
37        for k in range(sz):
38            x += 1
39            y -= 1
40            sum += grid[x][y]
41
42        # Go left up.
43        for k in range(sz):
44            x -= 1
45            y -= 1
46            sum += grid[x][y]
47
48        return sum

Java Solution

1
2java
3class Solution {
4    public int[] getBiggestThree(int[][] grid) {
5        int m = grid.length;
6        int n = grid[0].length;
7        TreeSet<Integer> sums = new TreeSet<>();
8
9        for (int i = 0; i < m; i++) {
10            for (int j = 0; j < n; j++) {
11                for (int sz = 0; i + sz < m && i - sz >= 0 && j + 2 * sz < n; sz++) {
12                    int sum = sz == 0 ? grid[i][j] : getSum(grid, i, j, sz);
13                    sums.add(sum);
14                    if (sums.size() > 3) {
15                        sums.pollFirst();
16                    }
17                }
18            }
19        }
20
21        int[] res = new int[sums.size()];
22        int index = res.length - 1;
23        for (int sum : sums) {
24            res[index--] = sum;
25        }
26        
27        return res;
28    }
29
30    // Returns rhombus sum of grid with top grid (i, j) and edge size `sz`.
31    private int getSum(int[][] grid, int i, int j, int sz) {
32        int x = i;
33        int y = j;
34        int sum = 0;
35
36        // Go left down.
37        for (int k = 0; k < sz; k++) {
38            sum += grid[--x][++y];
39        }
40
41        // Go right down.
42        for (int k = 0; k < sz; k++) {
43            sum += grid[++x][++y];
44        }
45
46        // Go right up.
47        for (int k = 0; k < sz; k++) {
48            sum += grid[++x][--y];
49        }
50
51        // Go left up.
52        for (int k = 0; k < sz; k++) {
53            sum += grid[--x][--y];
54        }
55
56        return sum;
57    }
58}

JavaScript Solution

1
2javascript
3var getBiggestThree = function(grid) {
4    const m = grid.length;
5    const n = grid[0].length;
6    const sums = new Set();
7
8    for (let i = 0; i < m; i++) {
9        for (let j = 0; j < n; j++) {
10            for (let sz = 0; i + sz < m && i - sz >= 0 && j + 2 * sz < n; sz++) {
11                const sum = (sz === 0) ? grid[i][j] : getSum(grid, i, j, sz);
12                sums.add(sum);
13                if (sums.size > 3) {
14                    sums.delete(Math.min(...sums));
15                }
16            }
17        }
18    }
19
20    return [...sums].sort((a, b) => b - a);
21
22    // Returns rhombus sum of grid with top grid (i, j) and edge size `sz`.
23    function getSum(grid, i, j, sz) {
24        let x = i;
25        let y = j;
26        let sum = 0;
27
28        // Go left down.
29        for (let k = 0; k < sz; k++) {
30            sum += grid[--x][++y];
31        }
32
33        // Go right down.
34        for (let k = 0; k < sz; k++) {
35            sum += grid[++x][++y];
36        }
37
38        // Go right up.
39        for (let k = 0; k < sz; k++) {
40            sum += grid[++x][--y];
41        }
42
43        // Go left up.
44        for (let k = 0; k < sz; k++) {
45            sum += grid[--x][--y];
46        }
47
48        return sum;
49    }
50};
💪
Level Up Your
Algo Skills

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫