Triangle
Find the minimum path sum from the top of a triangle to the bottom, moving to adjacent numbers on the row below.
- 1 <= triangle.length <= 200
- triangle[0].length == 1
- triangle[i].length == triangle[i - 1].length + 1
- -10⁴ <= triangle[i][j] <= 10⁴
Intuition
Triangle leetcode problem 120 finds the minimum path sum from the top of a triangle to the bottom, where each step moves to an adjacent number on the row below — index i or i + 1.
A greedy taking the smaller adjacent value fails, because a cheap step can lead into an expensive region. Every path must be considered, but paths overlap heavily, which is what a DP exploits.
Working top-down requires handling the row edges, since the first and last positions of each row have only one parent. Working bottom-up avoids that entirely:
- Starting from the bottom row and moving upward, every cell has exactly two children below it, so no boundary cases exist.
The recurrence is dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1]), and the answer ends up at dp[0][0] — a single value needing no final scan.
That is the real advantage of the bottom-up direction. Top-down leaves the answer spread across the last row, requiring a minimum over it, and demands edge handling throughout.
The bottom row needs no computation — a path ending there is just that cell's value — so it seeds the table directly.
Only the row below is ever read, so the table collapses to a single array of length n, updated in place from the bottom up. That gives O(n) space, which is what the problem's follow-up asks for.
When collapsing, iterate each row left to right, since dp[j] and dp[j+1] are both read before either is overwritten at position j.
The cost is O(n²) time — every cell is computed once — with O(n) space after the collapse.
Work bottom-up and the branching disappears. From the last row upward, each cell's best total is its own value plus the cheaper of the two cells below — and because the rows shrink, a single array reused in place holds the entire frontier.
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(n^2) for n rows time and O(n), reusing a single row of dp space.
Reject the greedy
Taking the smaller adjacent value fails, since a cheap step can lead into an expensive region. Paths overlap heavily, which suits a DP.
Work bottom-up
Every cell has exactly two children below it, so building upward has no boundary cases — unlike top-down, where row edges have one parent.
Seed the bottom row
A path ending in the last row is just that cell's value, so the bottom row copies the triangle directly with no computation.
Apply the recurrence
dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1]). Each cell takes the cheaper of its two downward continuations.
Read the answer at the apex
The result is dp[0][0], a single value. Top-down would instead leave the answer spread across the last row, needing a final minimum.
Collapse to one array
Only the row below is read, so a single array of length n suffices — the O(n) space the follow-up asks for. Iterate left to right when updating in place.
Cost of the tabulation
Every cell is computed once with O(1) work, giving O(n²) time and O(n) space after the collapse.
Solution & live demo
Common pitfalls
Going top-down and tracking two adjacency rules
dp[i][j] = triangle[i][j] + min(dp[i-1][j-1], dp[i-1][j])
dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
Top-down needs special handling at both ends of each row, where only one parent exists. Bottom-up always has exactly two children in range, so no boundary cases arise at all.
Iterating j upward while overwriting in place
# with a top-down formulation reusing one array
for j in range(i + 1):
dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])Bottom-up reads dp[j] and dp[j+1] — both still holding the lower row when j ascends, since only indices below j have been rewritten. The direction is safe here precisely because the reads look forward.
Copying the last row by reference
dp = triangle[-1]
dp = triangle[-1][:]
Without the slice, dp aliases the input's last row and the algorithm mutates the caller's data. It still returns the right answer, but the triangle is destroyed — a real bug if the input is reused.
Edge cases
The loop never runs; the answer is simply that one value.
min() still correctly favors the least (most negative) sum since no sign assumption is baked into the recurrence.
One iteration of the upward fill directly produces dp[0] = triangle[0][0] + min of the two bottom values.
min() picks either equally-valid path; the resulting sum is identical either way.