Triangle Minimum Path

Find the minimum path sum from top to bottom of a number triangle.

dynamic-programming bottom-up arrays path-sum

You are given a triangle represented as a list of lists, where the first row has one number, the second row has two numbers, and so on. From the top, you can move from a number in row i and column j to either the same column j or the next column j+1 in the row below (if they exist). Write a function `minimum_path_sum(triangle)` that returns the minimum possible sum of numbers along a path from the top of the triangle to the bottom (i.e., to any number in the last row). For example, for the triangle `[[2],[3,4],[6,5,7],[4,1,8,3]]`, the minimum path is `2 -> 3 -> 5 -> 1 = 11`.

Implement the function `minimum_path_sum(triangle: list[list[int]]) -> int`.

Constraints

- `triangle` has at least 1 row and at most 100 rows.
- Each row contains a number of elements equal to its 0-based index plus 1 (i.e., row `i` has `i+1` integers).
- Each integer is between -1000 and 1000 inclusive.
- The function must handle negative numbers correctly.
- Should run in O(n^2) time where n is the number of rows, using O(n) extra space or O(1) extra space if modifying the input.

Example

>>> minimum_path_sum([[2],[3,4],[6,5,7],[4,1,8,3]])
11
>>> minimum_path_sum([[-10]])
-10
>>> minimum_path_sum([[1],[2,3]])
3

12 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Start from the bottom row and move upward, updating each cell to be the sum of itself plus the minimum of its two adjacent children.

You can modify the triangle in place to avoid extra space.

After processing, the top cell contains the result.

Use `min(triangle[i+1][j], triangle[i+1][j+1])`.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.