Skip to content

2088. Count Fertile Pyramids in a Land 👍

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int countPyramids(vector<vector<int>>& grid) {
    int ans = count(grid);
    ranges::reverse(grid);
    ans += count(grid);
    return ans;
  }

 private:
  // dp[i][j] := the maximum height of the pyramid for which it is the apex
  int count(vector<vector<int>> dp) {
    int ans = 0;
    for (int i = dp.size() - 2; i >= 0; --i)
      for (int j = 1; j + 1 < dp[0].size(); ++j)
        if (dp[i][j] == 1) {
          dp[i][j] =
              min({dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1]}) + 1;
          ans += dp[i][j] - 1;
        }
    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public int countPyramids(int[][] grid) {
    return count(reversed(grid)) + count(grid);
  }

  // dp[i][j] := the maximum height of the pyramid for which it is the apex
  private int count(int[][] dp) {
    int ans = 0;
    for (int i = dp.length - 2; i >= 0; --i)
      for (int j = 1; j + 1 < dp[0].length; ++j)
        if (dp[i][j] == 1) {
          dp[i][j] = Math.min(dp[i + 1][j - 1], Math.min(dp[i + 1][j], dp[i + 1][j + 1])) + 1;
          ans += dp[i][j] - 1;
        }
    return ans;
  }

  private int[][] reversed(int[][] grid) {
    int[][] A = new int[grid.length][];
    for (int i = 0; i < grid.length; ++i)
      A[i] = grid[grid.length - i - 1].clone();
    return A;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def countPyramids(self, grid: list[list[int]]) -> int:
    # dp[i][j] := the maximum height of the pyramid for which it is the apex
    def count(dp: list[list[int]]) -> int:
      ans = 0
      for i in range(len(dp) - 2, -1, -1):
        for j in range(1, len(dp[0]) - 1):
          if dp[i][j] == 1:
            dp[i][j] = min(dp[i + 1][j - 1],
                           dp[i + 1][j],
                           dp[i + 1][j + 1]) + 1
            ans += dp[i][j] - 1
      return ans

    return count(deepcopy(grid)[::-1]) + count(grid)