Skip to content

1878. Get Biggest Three Rhombus Sums in a Grid 👎

  • Time: $O(n^4)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
 public:
  vector<int> getBiggestThree(vector<vector<int>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    set<int> sums;

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        for (int sz = 0; i + sz < m && i - sz >= 0 && j + 2 * sz < n; ++sz) {
          const int sum = sz == 0 ? grid[i][j] : getSum(grid, i, j, sz);
          sums.insert(sum);
          if (sums.size() > 3)
            sums.erase(sums.begin());
        }

    return vector<int>(sums.rbegin(), sums.rend());
  }

 private:
  // Returns the sum of the rhombus, where the top grid is (i, j) and the edge
  // size is `sz`.
  int getSum(const vector<vector<int>>& grid, int i, int j, int sz) {
    int x = i;
    int y = j;
    int sum = 0;

    // Go left down.
    for (int k = 0; k < sz; ++k)
      sum += grid[--x][++y];

    // Go right down.
    for (int k = 0; k < sz; ++k)
      sum += grid[++x][++y];

    // Go right up.
    for (int k = 0; k < sz; ++k)
      sum += grid[++x][--y];

    // Go left up.
    for (int k = 0; k < sz; ++k)
      sum += grid[--x][--y];

    return sum;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
  public int[] getBiggestThree(int[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;
    TreeSet<Integer> sums = new TreeSet<>();

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        for (int sz = 0; i + sz < m && i - sz >= 0 && j + 2 * sz < n; ++sz) {
          final int sum = sz == 0 ? grid[i][j] : getSum(grid, i, j, sz);
          sums.add(sum);
          if (sums.size() > 3)
            sums.pollFirst();
        }

    return sums.descendingSet().stream().mapToInt(Integer::intValue).toArray();
  }

  // Returns the sum of the rhombus, where the top grid is (i, j) and the edge
  // size is `sz`.
  private int getSum(int[][] grid, int i, int j, int sz) {
    int x = i;
    int y = j;
    int sum = 0;

    // Go left down.
    for (int k = 0; k < sz; ++k)
      sum += grid[--x][++y];

    // Go right down.
    for (int k = 0; k < sz; ++k)
      sum += grid[++x][++y];

    // Go right up.
    for (int k = 0; k < sz; ++k)
      sum += grid[++x][--y];

    // Go left up.
    for (int k = 0; k < sz; ++k)
      sum += grid[--x][--y];

    return sum;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
from sortedcontainers import SortedSet


class Solution:
  def getBiggestThree(self, grid: list[list[int]]) -> list[int]:
    m = len(grid)
    n = len(grid[0])
    sums = SortedSet()

    for i in range(m):
      for j in range(n):
        sz = 0
        while i + sz < m and i - sz >= 0 and j + 2 * sz < n:
          summ = grid[i][j] if sz == 0 else self._getSum(grid, i, j, sz)
          sums.add(summ)
          if len(sums) > 3:
            sums.pop(0)
          sz += 1

    return sums

  def _getSum(self, grid: list[list[int]], i: int, j: int, sz: int) -> int:
    """
    Returns the sum of the rhombus, where the top grid is (i, j) and the edge
    size is `sz`.
    """
    x = i
    y = j
    summ = 0

    # Go left down.
    for _ in range(sz):
      x -= 1
      y += 1
      summ += grid[x][y]

    # Go right down.
    for _ in range(sz):
      x += 1
      y += 1
      summ += grid[x][y]

    # Go right up.
    for _ in range(sz):
      x += 1
      y -= 1
      summ += grid[x][y]

    # Go left up.
    for _ in range(sz):
      x -= 1
      y -= 1
      summ += grid[x][y]

    return summ