Triangle minimum sum algorithm

It’s the weekend, which means I have time to catch up on sleep, get outside and of course, practice algorithms! For this problem, you are given an array of arrays arranged in the shape of a triangle, so that the first array has 1 item, the second has 2, the third has 3 and so on. If you write it the right way, it actually looks like a triangle:

The problem is to find the minimum path sum from the top to the bottom. By “path”, we mean starting at the top row, move down to an adjacent number of the next row and continue until you reach the bottom. By “path sum”, we mean the sum of all the numbers that make up a path. Taking our example above, we start on the first row and the number 2. From there, we can add either 3 or 4 from the second row. From 3, we can go to 6 or 5 on row 3. From 4, we can go to 5 or 7. And so on until we get to the last row. For this example, the minimum sum is 11: 2 +3+5+1.

Your first thought may be the brute force method. Go through every possible sum and find the smallest of these. This was my first thought as well but keeping track of all the possible paths with arrays and nested loops would involve a lot of time and space. There must be a better approach.

Instead of trying to calculate one sum at a time, we can make our way down the triangle, keeping track of the the smallest sum path for each element. We know every sum will start with our top number, 2. Moving down a level, the possible sums are 5 (2+3) and 6 (2+4).

On row 3 things start to get more interesting. The only path that leads to 6 comes from 3 and the only path that leads to 3 comes from 2. Therefore, the smallest sum that ends with 6 is 2+3+6=11. The same logic can be used to conclude that the smallest sum that leads to 7 (the 3rd element of row 3) is 13. For the middle element (5), there are 2 possible paths, from 3 and 4. We only care about the smaller one, so the smallest path sum for 5 is 10 (5 from Row 3, 3 from Row 2 and 2 from Row 1).

We continue with this pattern for each row. If we are at the first or last element in a row, then that number only has one “parent” so we simply add the parent’s smallest path sum to the number. If we are somewhere in the middle, then we add the smaller of the two parents’ paths. When we get to the last row, we will have the minimum path sum for each number in the last row. We simply take the smallest of these minimums to find the minimum of the entire triangle. Here it is in code:

If n is the number of elements in the triangle, then time complexity is O(n) since we only touch each number once. If n is the number of rows in the triangle, then time complexity is O(n^2) since we have to touch each row twice. Space complexity is O(n) since we need to create a results array of arrays that is the same size of the original input.

But since we’re just keeping track of the path sums in the results array, why can’t we just store these sums in the triangle itself? This would make it a destructive function, but would reduce our space complexity to O(1). This requires just a few changes to the code:

Here’s how our triangle looks after running the method:

We can see that the smallest number in the last row is 11, which must be the minimum path sum for the triangle!