Problem

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

OR

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

Input: triangle = [
    [2],
   [3,4],
  [6,5,7],
 [4,1,8,3]
]
Output: 11
Explanation: The triangle looks like:
   2̲
  3̲ 4
 6 5̲ 7
4 1̲ 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?

Similar Problem

Maximum Triangle path sum from top to bottom

Solution

The first mistake people make with this question is they fail to understand that you cannot simply traverse down the triangle taking the lowest number (greedy approach).

Method 1 - Recursive DFS

The problem resembles a tree structure where we need to find the minimum sum path from the root to a leaf.

  • At each step, choose between the left n or right n+1 path by selecting the smaller of the minimum path sums starting at nodes n and n+1 for row m-1.
  • This approach allows us to solve the problem by breaking it down into smaller subproblems.
  • Base Case: For the last row in the triangle, the minimum path sum is the value of the node itself.

Code

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

class Solution {
	public int minimumTotal(List<List<Integer>> triangle) {
	   return dfs(triangle, 0, 0).intValue();
	}
	
	public Integer dfs(List<List<Integer>> triangle, int rowNum, int index) {
	   List<Integer> row = triangle.get(rowNum);
	   // base case, we are at the last row
	   if (rowNum == triangle.size() - 1) {
	      return row.get(index);
	   }
	   int currentValue = row.get(index);
	   int minSumLeft = dfs(triangle, rowNum + 1, index);
	   int minSumRight = dfs(triangle, rowNum + 1, index + 1);
	   return currentValue + Math.min(minSumLeft, minSumRight);
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
   def minimumTotal(self, triangle: List[List[int]]) -> int:
      return self.dfs(triangle, 0, 0)
   
   def dfs(self, triangle: List[List[int]], row: int, idx: int) -> int:
      # base case, we are at the last row
      if row == len(triangle) - 1:
            return triangle[row][idx]
      current_value = triangle[row][idx]
      min_sum_left = self.dfs(triangle, row + 1, idx)
      min_sum_right = self.dfs(triangle, row + 1, idx + 1)
      return current_value + min(min_sum_left, min_sum_right)

Complexity

  • ⏰ Time complexity: O(2^n)
  • 🧺 Space complexity: O(n)

At each recursion call, we need to make the decision to traverse down the left or right path. Because of this, it is possible to reach any given node using two different paths. Looking at the recursion tree, we can see a duplicate calculation taking place for node with value 5 in the 3rd row.

graph TD;
	2 --- 3 & 4
	3 --- 6 & 5
	4 --- E2(5) & 7
	6 --- D2(4) & 1
	5 --- A1(1) & 8
	E2 --- A2(1) & H2(8)
	7 --- H3(8) & C(3)

We can do memoization / top down DP, but lets skip that for now.

Method 2 - Memoization

We can memoize the solution. We can use string key in the map with row number and index for each DFS call.

Code

 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

class Solution {
   private Map<String, Integer> memo = new HashMap<>();
   
   public int minimumTotal(List<List<Integer>> triangle) {
      return dfs(triangle, 0, 0);
   }
   
   public int dfs(List<List<Integer>> triangle, int rowNum, int index) {
      // base case, we are at the last row
      if (rowNum == triangle.size() - 1) {
            return triangle.get(rowNum).get(index);
      }
      
      // use a unique key for memoization
      String key = rowNum + "," + index;
      
      // check if result is already in memo
      if (memo.containsKey(key)) {
            return memo.get(key);
      }
      
      int currentValue = triangle.get(rowNum).get(index);
      int minSumLeft = dfs(triangle, rowNum + 1, index);
      int minSumRight = dfs(triangle, rowNum + 1, index + 1);
      
      // store result in memo
      int result = currentValue + Math.min(minSumLeft, minSumRight);
      memo.put(key, result);
      
      return result;
   }
}
 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

class Solution:
   def __init__(self):
      self.memo = {}
      
   def minimumTotal(self, triangle: List[List[int]]) -> int:
      return self.dfs(triangle, 0, 0)
   
   def dfs(self, triangle: List[List[int]], row: int, idx: int) -> int:
      # base case, we are at the last row
      if row == len(triangle) - 1:
            return triangle[row][idx]
      
      # use a unique key for memoization
      key = (row, idx)
      
      # check if result is already in memo
      if key in self.memo:
            return self.memo[key]
      
      current_value = triangle[row][idx]
      min_sum_left = self.dfs(triangle, row + 1, idx)
      min_sum_right = self.dfs(triangle, row + 1, idx + 1)
      
      # store result in memo
      result = current_value + min(min_sum_left, min_sum_right)
      self.memo[key] = result
      
      return result

Complexity

  • ⏰ Time complexity: O(n^2) – Each subproblem result is computed only once and stored in the memo.
  • 🧺 Space complexity: O(n^2) – The memoization table stores results for each subproblem, which in the worst case is proportional to the number of elements in the triangle.

Method 3 - Bottom up DP

The problem can be addressed using dynamic programming since it involves making decisions that minimize the total path sum at each level as follows:

1

dp[level][i] = triangle[level][i] + min{dp[next_level][i], dp[next_level][i+1]}

i.e.

1

minpath[k][i] = min(minpath[k+1][i], minpath[k+1][i+1]) + triangle[k][i];

Code

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

class Solution {
   public int minimumTotal(List<List<Integer>> triangle) {
      int levels = triangle.size();
      int[][] dp = new int[levels][levels];
      
      // Initialize the last row
      for (int i = 0; i < levels; i++) {
            dp[levels - 1][i] = triangle.get(levels - 1).get(i);
      }

      // Bottom-up calculation
      for (int l = levels - 2; l >= 0; l--) {
            for (int i = 0; i <= l; i++) {
               dp[l][i] = Math.min(dp[l + 1][i], dp[l + 1][i + 1]) + triangle.get(l).get(i);
            }
      }
      return dp[0][0];
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
   def minimumTotal(self, triangle: List[List[int]]) -> int:
      levels = len(triangle)
      dp = triangle[-1][:]

      # Bottom-up calculation
      for l in range(levels - 2, -1, -1):
            for i in range(l + 1):
               dp[i] = min(dp[i], dp[i + 1]) + triangle[l][i]
               
      return dp[0]

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(n^2)

If we print the dp table for an example triangle, it appears as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

Triangle -

[2],
[3,4],
[6,5,7],
[4,1,8,3]

dp table  -

11, 0, 0, 0
9, 10, 0, 0
7,  6, 10, 0
4,  1,  8, 3

The table has meaningful values in the lower half, and at each level, one of the columns gets fixed moving bottom-up. Thus, we can use the bottom level array as the dp table and update the columns bottom-up, reducing the space complexity from O(n^2) to O(n).

Method 4 - Space Optimal Bottom-up DP

We can solve this problem using a bottom-up dynamic programming approach.

  • Begin from the second last row and update each element by adding the minimum of the adjacent numbers from the row below.
  • The solution will be at the top of the triangle.

To optimize space, we focus on the recurrence relation:

1

minpath[k][i] = min(minpath[k+1][i], minpath[k+1][i+1]) + triangle[k][i];

Since minpath[k+1] becomes irrelevant after minpath[k] is computed, we can use a 1D array and update it iteratively:

1

minpath[i] = min(minpath[i], minpath[i+1]) + triangle[k][i];

Thus, the dynamic programming relation is:

1

dp[i] = triangle.get(level).get(i) + Math.min(dp[i], dp[i+1]);

Here is the approach:

  • Start from the second last row and keep adding the minimum of the adjacent numbers from the row below to each element.
  • The final answer will be at the top of the triangle.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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

class Solution:
   def minimumTotal(self, triangle: List[List[int]]) -> int:
      size = len(triangle)
      if size == 0:
            return 0
      for i in range(size - 2, -1, -1):
            for j in range(len(triangle[i])):
               triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1])
      return triangle[0][0]

Complexity

  • ⏰ Time complexity: O(n^2) due to the nested loops iterating through the triangle.
  • 🧺 Space complexity: O(1) as we are modifying the triangle in place without using additional storage.