Triangle

Medium#120from the bottom up

Numbers are stacked in a triangle: one in the first row, two in the second, and so on. Walk from the top to the bottom row; from a cell you may step to either of the two cells right under it. Find the smallest sum of the numbers on such a walk. Our example: [2], [4, 1], [3, 8, 9], [1, 6, 7, 2], the answer is 10.

120 TriangleWalkthrough · 1×

Example: a triangle of 4 rows. The 1 in row 1 looks like the better start, but everything under it is dear: from the bottom up it ends with 12 against 8 for the 4 next to it.

trianglebest22441133889911667722
a number of the trianglecheapest way down from this cellthis stepread fromthe cheapest walk

best starts as a copy of the triangle. The bottom row is already right: from a cell there the way down is the cell alone

01/23
restart · back · play · step
Speed
1function minimumTotal(tri):
2 best = copy of tri
3 for r from len(tri) - 2 down to 0:
4 for c from 0 to r:
5 left = best[r + 1][c]
6 right = best[r + 1][c + 1]
7 best[r][c] = tri[r][c] + min(left, right)
8 return best[0][0]
state
best
[[2], [4, 1], [3, 8, 9], [1, 6, 7, 2]]
r
–
c
–
left
–
right
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. From a cell, the cheapest way down is its own number plus the cheaper of the cheapest ways down from the two cells under it. Going row by row from the bottom, those two are always ready.
  2. Every cell of the bottom row is a finished walk on its own, so the copy of the triangle already holds the right values there, and nothing else needs a base case.
  3. Choosing the cheaper cell on the way down looks only one row ahead: here it takes the 1 and pays 17. Each cell of best has already seen every walk below it.

Complexity

Time O(n²) for n rows: each of the about n²/2 cells is one min and one addition. Memory O(n²) for the copy; a row reads only the row under it, so one array of n numbers is enough.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.