Triangle

The trap is visible: every row offers two choices, so it is tempting to choose the smaller child or enumerate every path. The reliable Triangle solution works differently: compute the best continuation beneath each cell, from the bottom upward.

Read the contract before choosing a pattern

For a cell at triangle[row][col], the next row permits exactly two moves:

• triangle[row + 1][col]
• triangle[row + 1][col + 1]

The path starts at the sole element in the top row and must finish somewhere in the bottom row. The output is the minimum sum, not the path itself.

The constraints guarantee at least one row. With r rows, row i contains i + 1 values, and values may be negative.

One classification detail matters here: although the recurrence reads two neighboring indices, this is not fundamentally a Two Pointers problem. Two pointers are useful when coordinated index movement eliminates impossible candidates or shrinks a search range. Triangle has no such movement rule. Its structure is overlapping subproblems: many possible paths share the same remaining subtriangle. Dynamic programming is the right lens.

Why the obvious approaches fail

A direct recursive formulation is easy to write:

1. Add the current cell.
2. Recursively solve the two children.
3. Keep the smaller completed path.

Conceptually:

best(row, col) =
    triangle[row][col] +
    min(best(row + 1, col), best(row + 1, col + 1))

The problem is repeated work. Different routes reach the same cell, and each recursive call recomputes the same continuation. With r rows, the number of possible left/right choices grows exponentially, roughly as 2^(r - 1).

Greedy selection fails for a different reason. The smaller immediate child may lead to a much worse continuation. For example:

[0]
[1, 2]
[100, -100, 0]

Choosing 1 because it is smaller than 2 leads to 1 + 100. Choosing 2 leads to 2 - 100, which is much better. The decision must compare complete continuation sums, not just the next value.

That failed greedy instinct points toward the state we actually need: the best result from each cell to the bottom.

Define the state from the bottom up

Let:

dp[row][col]

represent the minimum sum starting at triangle[row][col] and continuing to any valid cell in the bottom row.

The last row is the base case. A cell there has nowhere else to go, so its minimum continuation sum is simply its own value:

dp[last_row][col] = triangle[last_row][col]

For every earlier cell, the two possible continuations are already described by the cells below it:

dp[row][col] =
    triangle[row][col] +
    min(dp[row + 1][col], dp[row + 1][col + 1])

The traversal order is forced by the dependencies. Both states on the row below must be known before the current state can be finalized, so process rows from bottom to top.

Consider:

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

Start with the bottom row:

[4, 1, 8, 3]

Process [6, 5, 7]:

6 + min(4, 1) = 7
5 + min(1, 8) = 6
7 + min(8, 3) = 10

The best continuation values for that row are:

[7, 6, 10]

Now process [3, 4]:

3 + min(7, 6) = 9
4 + min(6, 10) = 10

Finally:

2 + min(9, 10) = 11

The minimum path sum is 11, produced by the path 2 → 3 → 5 → 1.

The important shift is small but decisive: we are not guessing a path from the top. We are turning every cell into a reusable answer about the subproblem below it.

Compress the state to one dimension

A full two-dimensional DP table works, but each row depends only on the row immediately below it. There is no reason to retain every completed row.

Use a one-dimensional array initialized from the bottom row:

dp = triangle[-1][:]

When processing a row, update dp[col] in place:

dp[col] = triangle[row][col] + min(dp[col], dp[col + 1])

Before the assignment:

• dp[col] is the continuation value for the lower cell at column col.
• dp[col + 1] is the continuation value for the lower cell at column col + 1.

Iterate col from left to right. The assignment overwrites dp[col], but that old value is no longer needed. The value at dp[col + 1] has not been overwritten yet, so it remains the second child required by the recurrence.

For the example above, the one-dimensional state changes like this:

Processed state	dp
Bottom row copied	[4, 1, 8, 3]
Process [6, 5, 7]	[7, 6, 10, 3]
Process [3, 4]	[9, 10, 10, 3]
Process [2]	[11, 10, 10, 3]

Only dp[0] matters at the end.

There is another possible optimization: update triangle itself in place. That uses constant auxiliary space, but it mutates the caller's input. I prefer the copied bottom row for an interview answer because it keeps the input unchanged while still meeting the required O(r) extra-space target.

Prove the recurrence and implementation

The correctness argument is an induction from the bottom upward.

Base case: Every cell in the last row has no legal move below it. Its minimum path sum is therefore its own value. The initialization is correct.

Inductive step: Assume the two children beneath triangle[row][col] already store their minimum continuation sums. Every valid path from the current cell must choose one of those two children. Therefore, the best path from the current cell is its own value plus the smaller of the two optimal child continuations:

triangle[row][col] +
min(dp[row + 1][col], dp[row + 1][col + 1])

That computes the optimal value for the current state. Repeating this through the top row makes dp[0] the minimum valid path sum for the entire triangle.

The compressed array preserves the same logic with a rolling invariant:

Before processing a row, the relevant entries of dp contain minimum continuation sums for the row directly below. During the update, dp[col] and dp[col + 1] are still the two required child values.

The left-to-right traversal preserves that invariant because dp[col + 1] remains untouched when dp[col] is calculated.

Negative values require no special handling. The recurrence compares complete path sums, so it does not assume that values increase, remain positive, or behave monotonically.

Implement Triangle in Python

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

        for row in range(n - 2, -1, -1):
            for col in range(len(triangle[row])):
                dp[col] = triangle[row][col] + min(dp[col], dp[col + 1])

        return dp[0]

Each part of the implementation has a direct obligation:

• triangle[-1][:] creates the base-case continuation values without mutating the input.
• range(n - 2, -1, -1) processes every non-bottom row after its dependencies are ready.
• dp[col] and dp[col + 1] represent the two legal moves from the current cell.
• min(...) selects the better complete continuation.
• dp[0] is the state for the top element after all rows have been folded upward.

The problem contract guarantees a nonempty triangle, so this implementation intentionally does not add an empty-input branch. If you were writing a general-purpose utility with a broader contract, you would decide separately what an empty input should mean.

Complexity, edge cases, and interview checks

With r rows, the triangle contains:

1 + 2 + 3 + ... + r = r(r + 1) / 2

cells. The algorithm visits each cell once:

• Time: O(r²)
• Extra space: O(r)

The O(r) space refers to the number of rows, not the total number of input values. The input itself contains O(r²) values.

Check these cases before you trust the implementation:

A single-row triangle

[[7]]

The bottom row is also the top row. The copied dp is [7], no update loop runs, and the answer is 7.

Negative and mixed values

Do not initialize a minimum with zero. Zero is not a valid default path value and can incorrectly beat an all-positive or all-negative continuation.

Do not compare only the two immediate children. The correct comparison is between the two child subproblem results, which already include everything beneath them.

Row boundaries

The outer loop must stop at 0, not process the bottom row again:

range(n - 2, -1, -1)

For a current cell at column col, the second child is always col + 1. The triangular shape guarantees that this index exists in the next row.

Input mutation

An in-place version is shorter:

for row in range(len(triangle) - 2, -1, -1):
    for col in range(len(triangle[row])):
        triangle[row][col] += min(
            triangle[row + 1][col],
            triangle[row + 1][col + 1],
        )

return triangle[0][0]

Its auxiliary space is O(1), but the input is changed. That tradeoff should be explicit. Space complexity is not the only contract an implementation must respect.

The reusable recognition rule

When a grid or tree-like structure offers a small fixed set of next moves, ask whether different routes merge into the same remaining subproblem.

If they do, use this sequence:

1. Name the state. What does the best answer from one position mean?
2. List its dependencies. Which smaller states are required?
3. Choose dependency order. Compute those states before the current one.
4. State the invariant. What does every stored value mean before and after an update?
5. Compress only after the recurrence is clear.

This is also the classification rule that prevents the Two Pointers mismatch. The presence of two indices does not make a problem a two-pointer problem. Ask what the indices do:

• If they move to discard impossible ranges, think two pointers.
• If they identify overlapping child states in a recurrence, think dynamic programming.

Triangle is a recurrence-derivation problem, not a path-guessing exercise. Before coding a new instance, draw a small triangle, write the meaning of one state, and mark its dependencies. Then make the loop follow that dependency order. Clear the noise. Find the state. Compute upward.