Triangle Minimum Path Sum

Find the cheapest way down a triangle of numbers, one step to the row below at a time.

Given a triangle of numbers, where the first row has one number, the second two, and so on, return the smallest sum of a path from the top row to the bottom row. From index i in a row, the path may step to index i or index i + 1 in the next row.

Example 1
Input: triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
Output: 11
Explanation: the path 2, 3, 5, 1 adds up to 11.
Example 2
Input: triangle = [[-10]]
Output: -10
Solution

The Idea

Picture a pyramid of numbered blocks. You start on the block at the top and climb down one row at a time, and from each block you may step onto one of the two blocks right under it. Every block you stand on adds its number to your total, and you want the smallest total at the bottom.

Write Example 1 as a pyramid. The top block is 2, and under it sit 3 and 4. Under 3 sit 6 and 5, and under 5 sit 1 and 8. The walk 2, 3, 5, 1 adds up to 11, and no other walk down does better. With four rows there are eight walks in all, because each of the three steps has two choices.

Why not just step onto the smaller block each time? In Example 1 that happens to give 2, 3, 5, 1. But take the pyramid [[1], [2, 3], [9, 9, 1]]. From 1 the smaller block is 2, and under 2 there are only two 9s, so the walk ends at 12. The walk 1, 3, 1 costs 5. A cheap block now can lead to expensive blocks later.

So the choice at a block depends on what lies below it. That suggests starting at the bottom. For a block in the bottom row, the cheapest way down is just its own number. For a block one row higher, it is its own number plus the cheaper of the two blocks under it.

Left: the triangle 2; 3, 4; 6, 5, 7; 4, 1, 8, 3 with the path 2, 3, 5, 1 highlighted. Right: the same shape holding the cheapest sum from each cell down: 11; 9, 10; 7, 6, 10; 4, 1, 8, 3.

Look at the picture above. On the left is the triangle from Example 1, with the cheapest path 2 + 3 + 5 + 1 in orange. On the right, headed “cheapest sum from this cell down”, each block holds the best total from that block to the bottom. Row 3, the bottom row, keeps its own numbers. In row 2, the block 5 becomes 5 + min(1, 8) = 6, as the first teal line under the picture shows.

Row 1 works the same way: 3 + min(7, 6) = 9 and 4 + min(6, 10) = 10. At the top, 2 + min(9, 10) = 11, which is the answer. Each block was worked out once, and the row above simply read the two numbers under it.

Working out the best total for each block once, and letting the blocks above build on those totals instead of walking every path again, is called dynamic programming.

Solution Approach

Turning that idea into code means looking at why trying every path is slow, then settling two things: which direction to fill the rows, and where to keep the totals.

Trying every path

How many paths are there? Each step down offers two choices, so a triangle with n rows has 2n-1 paths: 8 for Example 1, but more than 500,000 for 20 rows. A search that walks each one adds up the same lower parts again and again, since many paths pass through the same block.

Filling the rows from the bottom up

Which row should come first? The best total for a block needs the two totals under it, so the bottom row comes first and the top row last. A block at row r, index i, gets its own number plus the smaller of the totals at index i and index i + 1 in row r + 1.

Going upward also ends neatly. The top row has a single block, so its total is the answer, and there is no need to compare several end points at the bottom.

Working from the top down is possible too, with a method that calls itself for the two blocks below and remembers each result. It finds the same totals, but needs a table for the stored results and a call for each block.

One array for the totals

Do we need a whole triangle of totals? Each row only reads the row right under it, so a single array, named below, is enough. It has one slot more than the bottom row has numbers, and starts as all zeros, the cost of going past the bottom row.

Each row writes its totals over the old ones, from left to right. Writing below[i] needs the old values at index i and index i + 1. The old value at index i is read just before it is replaced, and index i + 1 is not replaced until the next step.

The extra slot lets the bottom row's last block read below[i + 1] like any other block. After row 2 of Example 1, below holds [7, 6, 10, 3, 0]. The 3 and the 0 are left over from earlier rows, and row 1, with two blocks, never reads past index 2.

Java Solution

The method minimumTotal works in these steps:

  1. First, create the array below with n + 1 zeros, where n is the number of rows.
  2. Go over the rows from the bottom up with a loop over r, from n - 1 down to 0, and take that row as row.
  3. Inside, a second loop moves i over the blocks of row from left to right. It sets below[i] to the block's number plus the smaller of below[i] and below[i + 1], the two totals under it.
  4. When the top row is done, below[0] holds the cheapest total from the top block down, and the method returns it.

The main method runs both examples, the pyramid [[1], [2, 3], [9, 9, 1]] where stepping onto the smaller block fails, and a triangle with negative numbers.

Java
import java.util.List;

public class TriangleMinPathSum {

    public static int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] below = new int[n + 1];          // cheapest sums from the row below; zeros at first
        for (int r = n - 1; r >= 0; r--) {
            List<Integer> row = triangle.get(r);
            for (int i = 0; i < row.size(); i++) {
                // this cell plus the cheaper of the two cells under it
                below[i] = row.get(i) + Math.min(below[i], below[i + 1]);
            }
        }
        return below[0];
    }

    public static void main(String[] args) {
        System.out.println(minimumTotal(List.of(
                List.of(2), List.of(3, 4), List.of(6, 5, 7), List.of(4, 1, 8, 3))));
        System.out.println(minimumTotal(List.of(List.of(-10))));
        System.out.println(minimumTotal(List.of(
                List.of(1), List.of(2, 3), List.of(9, 9, 1))));
        System.out.println(minimumTotal(List.of(
                List.of(-1), List.of(2, 3), List.of(1, -1, -3))));
    }
}

Running it prints:

Output
11
-10
5
-1

The 11 and the -10 match Examples 1 and 2. For a triangle with a single row, the outer loop runs once and below[0] becomes -10 + min(0, 0).

The third line, 5, is the walk 1, 3, 1 through [[1], [2, 3], [9, 9, 1]]. A separate check that always steps onto the smaller block gets 12 on that pyramid, because it takes 2 and then has only 9s below. The last line, -1, comes from [[-1], [2, 3], [1, -1, -3]]: the path -1, 3, -3. The starting zeros in below add nothing to a sum, so negative numbers need no special care.

The original implementation, TriangleMinPathSum.java, is on GitHub.

Complexity

The work is one update of below for each block of the triangle.

  • Time: O(n²), because a triangle of n rows has 1 + 2 + ... + n, about n²/2 blocks, and each block costs one addition and one Math.min.
  • Space: O(n), because below holds n + 1 totals, one row's worth, while the triangle itself is only read and never copied.

A square version, where each step down has three choices, is Minimum Falling Path Sum.