Problem

You are given an array of arrays of integers, where each array corresponds to a row in a triangle of numbers. For example, [[1], [2, 3], [1, 5, 1]] represents the triangle:

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: triangle = [
    [1],
   [2,3],
  [1,5,1],
]
Output: 9
Explanation: The path 1 -> 3 -> 5 (underlined) has the maximum weight of 9.
   1̲̲
  2 3̲
 1 5̲ 1

Similar Problem

Minimum Triangle path sum from top to bottom

Solution

Method 1 - Space optimized DP

To find the maximum weight path in the triangle, we can use dynamic programming. We start from the bottom of the triangle and move upwards, updating each value to be the sum of itself and the maximum of the adjacent values from the row below. This way, each value at the top will be the greatest possible sum of the path from the bottom to that point.

Here is the approach:

  1. Start from the second last row and move upwards to the top row.
  2. For each element in the current row, update it by adding the maximum of the adjacent values from the row below.
  3. The top element of the triangle will contain the maximum weight path sum after processing all rows.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

public class Solution {
    public int maximumTotal(int[][] triangle) {
        int n = triangle.length;
        for (int row = n - 2; row >= 0; row--) {
            for (int col = 0; col < triangle[row].length; col++) {
                triangle[row][col] += Math.max(triangle[row + 1][col], triangle[row + 1][col + 1]);
            }
        }
        return triangle[0][0];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] triangle1 = {{1}, {2, 3}, {1, 5, 1}};
        System.out.println(solution.maximumTotal(triangle1)); // Output: 9

        int[][] triangle2 = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
        System.out.println(solution.maximumTotal(triangle2)); // Output: 23
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def maximumTotal(self, triangle):
        n = len(triangle)
        for row in range(n - 2, -1, -1):
            for col in range(len(triangle[row])):
                triangle[row][col] += max(triangle[row + 1][col], triangle[row + 1][col + 1])
        return triangle[0][0]

if __name__ == "__main__":
    solution = Solution()
    triangle1 = [[1], [2, 3], [1, 5, 1]]
    print(solution.maximumTotal(triangle1)) # Output: 9

    triangle2 = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
    print(solution.maximumTotal(triangle2)) # Output: 23

Complexity

  • ⏰ Time complexity: O(n^2), where n is the number of rows in the triangle since we need to process each element.
  • 🧺 Space complexity: O(1), since we are modifying the triangle in place.