Skip to content

120. Triangle 👍

  • Time: $O(n^2)$
  • Space: $O(1)$
1
2
3
4
5
6
7
8
9
class Solution {
 public:
  int minimumTotal(vector<vector<int>>& triangle) {
    for (int i = triangle.size() - 2; i >= 0; --i)
      for (int j = 0; j <= i; ++j)
        triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);
    return triangle[0][0];
  }
};

1
2
3
4
5
6
7
8
9
class Solution {
  public int minimumTotal(List<List<Integer>> triangle) {
    for (int i = triangle.size() - 2; i >= 0; --i)
      for (int j = 0; j <= i; ++j)
        triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i + 1).get(j),
                                                                 triangle.get(i + 1).get(j + 1)));
    return triangle.get(0).get(0);
  }
}

1
2
3
4
5
6
7
8
class Solution:
  def minimumTotal(self, triangle: list[list[int]]) -> int:
    for i in reversed(range(len(triangle) - 1)):
      for j in range(i + 1):
        triangle[i][j] += min(triangle[i + 1][j],
                              triangle[i + 1][j + 1])

    return triangle[0][0]