LeetCode 120: Triangle

Problem Restatement

We are given a triangle array.

Each row has one more element than the previous row.

Starting from the top, we may move only to one of the two adjacent numbers directly below:

• Same index
• Next index

We must find the minimum path sum from top to bottom.

The official problem defines adjacency exactly this way. (leetcode.com)

For example:

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

One valid path is:

2 -> 3 -> 5 -> 1

Its sum is:

11

This is the minimum possible sum, so the answer is:

11

Input and Output

The function shape is:

class Solution:
    def minimumTotal(self, triangle: list[list[int]]) -> int:
        ...

Examples

Consider:

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

Possible paths include:

2 -> 3 -> 6 -> 4 = 15
2 -> 3 -> 5 -> 1 = 11
2 -> 4 -> 5 -> 1 = 12
2 -> 4 -> 7 -> 3 = 16

The minimum is:

11

Now consider:

triangle = [
    [-10]
]

The answer is:

-10

because there is only one possible path.

First Thought: Try Every Path

At each row, we have two choices:

1. Move downward.
2. Move down-right.

That creates a binary decision tree.

For a triangle with many rows, the number of paths grows exponentially.

We need dynamic programming because many subproblems repeat.

Key Insight

Suppose we are at:

triangle[i][j]

The best path from this position depends only on:

1. The best path below it.
2. The best path down-right from it.

So:

This suggests a bottom-up approach.

Start from the last row, which already contains complete path sums.

Then move upward row by row.

Bottom-Up Dynamic Programming

Suppose the bottom row is:

[4, 1, 8, 3]

These values are already final path sums because no rows exist below them.

Now process the row above:

[6, 5, 7]

For 6:

6 + min(4, 1) = 7

For 5:

5 + min(1, 8) = 6

For 7:

7 + min(8, 3) = 10

Now the row becomes:

[7, 6, 10]

Repeat upward until reaching the top.

The top value becomes the minimum path sum.

Algorithm

Create a copy of the last row:

dp = triangle[-1][:]

Then process rows upward:

For each row i from bottom-1 to top:

For each column j:

At the end:

dp[0]

contains the minimum total.

Correctness

The algorithm processes the triangle from bottom to top.

Initially, dp[j] stores the minimum path sum starting from the bottom-row element:

triangle[last_row][j]

This is correct because no further moves are possible.

Now consider a higher position:

triangle[i][j]

From this position, the next move can go only to:

triangle[i+1][j]
triangle[i+1][j+1]

By the induction hypothesis, dp[j] and dp[j+1] already store the minimum path sums starting from those two positions.

Therefore, the minimum path sum starting at:

triangle[i][j]

is:

Updating dp[j] with this value is correct.

After processing all rows upward, dp[0] stores the minimum path sum from the top of the triangle to the bottom.

Thus, the algorithm correctly computes the minimum total.

Complexity

Here, n is the number of rows.

The triangle contains approximately:

values total.

Implementation

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

        for i in range(len(triangle) - 2, -1, -1):
            for j in range(len(triangle[i])):
                dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])

        return dp[0]

Code Explanation

Copy the last row:

dp = triangle[-1][:]

These are the initial minimum path sums.

Process rows upward:

for i in range(len(triangle) - 2, -1, -1):

Process every value in the row:

for j in range(len(triangle[i])):

Update the minimum path sum:

dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])

dp[j] and dp[j+1] represent the two reachable positions below.

Finally:

return dp[0]

The top value becomes the answer.

Testing

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

        for i in range(len(triangle) - 2, -1, -1):
            for j in range(len(triangle[i])):
                dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])

        return dp[0]

def run_tests():
    s = Solution()

    assert s.minimumTotal([
        [2],
        [3, 4],
        [6, 5, 7],
        [4, 1, 8, 3]
    ]) == 11

    assert s.minimumTotal([
        [-10]
    ]) == -10

    assert s.minimumTotal([
        [1],
        [2, 3]
    ]) == 3

    assert s.minimumTotal([
        [5],
        [9, 6],
        [4, 6, 8],
        [0, 7, 1, 5]
    ]) == 18

    print("all tests passed")

run_tests()

Test meaning: