Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Triangle
• Topics: Array, Dynamic Programming

Problem gist

The input is a triangle of numbers. A path starts at the top and moves down one row at a time. From position (row, column), the next value must be either directly below at (row + 1, column) or diagonally below-right at (row + 1, column + 1).

The goal is to return the smallest possible sum from the top to the bottom.

A greedy choice is not reliable. Taking the smaller of the two immediate children can lead into very expensive values later, while a slightly larger child may open a much cheaper route. The decision at each cell therefore depends on the best complete path below each child.

Deriving the dynamic programming solution

Define:

cost(row, column) = the minimum path sum from this cell to the bottom

Every non-bottom cell has exactly two possible next steps, so its recurrence is:

cost(row, column) = triangle[row][column] + min(cost(row + 1, column), cost(row + 1, column + 1))

The bottom row is the base case because each value there is already the full cost of a path ending at that cell.

This recurrence naturally suggests working upward:

1. Copy the bottom row into a one-dimensional array of minimum costs.
2. Visit each higher row from bottom to top.
3. Replace each cost with the current value plus the cheaper of its two child costs.
4. After processing the top row, the first cost is the answer.

For the triangle [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]], the cost array changes as follows:

• Start with the bottom row: [4, 1, 8, 3]
• Fold in [6, 5, 7]: [7, 6, 10]
• Fold in [3, 4]: [9, 10]
• Fold in [2]: [11]

The minimum path sum is 11.

Why one row of memory is enough

When processing a row, the algorithm only needs the already-computed costs for the row immediately below it. Earlier rows are not used yet, and lower rows will never be needed again.

The cost array can therefore be updated in place. At column j, its two child costs are still available at positions j and j + 1. This reduces auxiliary space from the number of cells in the triangle to the width of its last row.

Python solution

from collections.abc import Sequence
from typing import List


class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        """Return the minimum top-to-bottom path sum without changing the input."""
        if not triangle:
            return 0

        return self._minimum_path_sum_bottom_up(triangle)

    @staticmethod
    def _minimum_path_sum_bottom_up(
        triangle: Sequence[Sequence[int]],
    ) -> int:
        # Each entry stores the cheapest path from the current position
        # through the part of the triangle already processed below it.
        minimum_costs = list(triangle[-1])

        for row_index in range(len(triangle) - 2, -1, -1):
            current_row = triangle[row_index]

            for column_index, value in enumerate(current_row):
                cheaper_child_cost = min(
                    minimum_costs[column_index],
                    minimum_costs[column_index + 1],
                )
                minimum_costs[column_index] = value + cheaper_child_cost

        return minimum_costs[0]

Complexity

Let N be the total number of values in the triangle and R be the number of rows.

• Time: O(N), because every value is processed once.
• Auxiliary space: O(R), because the last row has R entries.

The input is not modified. If modifying it is allowed, the same recurrence can be written directly into the triangle for O(1) auxiliary space.

Interview follow-ups

How would the solution return the actual minimum-sum path?

Store the chosen child direction for every non-bottom cell while computing costs. For each cell, record whether the left child or right child produced the smaller cost. Then start at the top and follow those recorded decisions to reconstruct the path.

The cost calculation remains O(N), and reconstruction takes O(R). Recording a decision for each cell uses O(N) additional space. Keeping only one cost row is not enough for later reconstruction because those choices are overwritten as the algorithm moves upward.

Can the auxiliary space be reduced to constant space?

Yes, if the interviewer allows the input triangle to be modified. Starting with the second-to-last row, replace each cell with its value plus the smaller of its two children. The answer eventually appears at triangle[0][0].

This keeps O(N) time and uses O(1) auxiliary space, but it destroys the original values. The one-dimensional approach is usually the better production default because it preserves caller-owned input while still using only O(R) space.

What changes if the triangle arrives one row at a time?

A streamed triangle cannot be processed bottom-up because future rows are not available yet. Use top-down dynamic programming instead. For every value in the new row, add the smaller reachable cost from the previous row: the parent at the same column or the parent one column to the left. Missing parents at the row boundaries are treated as unreachable.

Only the previous row of costs must be retained, so the space remains O(R). The time remains O(N). The final answer is the minimum cost in the last computed row rather than a single value at the top.

How would blocked cells or additional allowed moves affect the solution?

Treat every cell as a vertex in a directed acyclic graph. Each allowed downward move becomes an edge, and blocked cells are omitted or assigned an unreachable cost. Process vertices in row order for a top-down solution or reverse row order for a bottom-up solution.

The same shortest-path dynamic programming idea still works because every edge moves to a later row, so cycles cannot exist. The complexity becomes O(V + E), where V is the number of usable cells and E is the number of allowed moves.

How would the solution count the number of minimum-sum paths?

Store a pair for each state: the minimum cost and the number of ways to achieve that cost. When one child has a smaller cost, inherit only that child’s count. When both child costs are equal, add their counts because either continuation produces a minimum path.

This does not change the asymptotic running time. It requires storing both a cost and a count per active position, so the optimized version still uses O(R) auxiliary space.

Would Dijkstra’s algorithm be an appropriate alternative?

The triangle can be modeled as a graph, but Dijkstra’s algorithm is unnecessary and may be invalid when values are negative. The graph is already acyclic, so dynamic programming processes each cell and edge once without a priority queue.

For the standard two-child triangle, dynamic programming runs in O(N) time. Dijkstra’s algorithm would add heap overhead and obscure the simpler recurrence that the triangle structure provides.