Triangle — InterviewPrepKit

Solving tips

best(i,j) = triangle[i][j] + min(best(i+1,j), best(i+1,j+1)); fill bottom-up so every cell has both children ready.
Bottom-up dodges the edge cases that plague top-down (leftmost/rightmost cells have only one valid parent above).
Collapse to a single length-n array seeded from the bottom row, overwriting left-to-right, for O(n) space (meets the follow-up).
Values can be negative, so greedy 'always pick the smaller next cell' fails - only the DP is correct. O(n^2) time.

Problem

You’re given a triangle as a list of rows, where row i has i + 1 numbers. Starting at the single top element, walk down to the bottom row, adding the numbers you step on. From position j in a row you may step to position j or j + 1 in the row below (the two entries directly beneath). Return the minimum possible path sum from top to bottom.

Examples

triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] → 11 — path 2 → 3 → 5 → 1.
triangle = [[-10]] → -10 — a single element is the whole path.
triangle = [[1],[2,3]] → 3 — 1 → 2; choosing 3 would give 4.

Constraints

1 <= triangle.length <= 200
triangle[i].length == i + 1
-10⁴ <= triangle[i][j] <= 10⁴
Follow-up: solve using only O(n) extra space, where n is the number of rows.

Think about it first

Hint 1

From cell (i, j), the best you can do is triangle[i][j] plus the cheaper of the two cells you can reach below it. That's a recurrence begging for memoization.

Hint 2

best(i, j) = triangle[i][j] + min(best(i+1, j), best(i+1, j+1)), with the bottom row as the base case. The answer is best(0, 0).

Hint 3

Fill it bottom-up: start from the last row and collapse upward. Each cell overwrites into a single 1-D array of length n, since row i needs only the already-computed row i+1.

TL;DR

Bottom-up DP collapsing each row into a 1-D array — O(n²) time (n² cells), O(n) space.

Approach 1 — Brute-force recursion

From the top, try both downward steps at every cell and keep the cheaper total.

Recurrence: best(i, j) = triangle[i][j] + min(best(i+1, j), best(i+1, j+1)). Base: on the last row, best(i, j) = triangle[i][j].

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

        def best(i: int, j: int) -> int:
            if i == n - 1:
                return triangle[i][j]
            below = min(best(i + 1, j), best(i + 1, j + 1))
            return triangle[i][j] + below

        return best(0, 0)

Complexity: each cell spawns two calls and cells are revisited → O(2ⁿ) time. At n = 200 this is astronomically slow.

Approach 2 — Memoized top-down

The insight: best(i, j) depends only on (i, j), and there are 1 + 2 + ... + n = O(n²) such cells. Cache them.

from functools import lru_cache

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

        @lru_cache(maxsize=None)
        def best(i: int, j: int) -> int:
            if i == n - 1:
                return triangle[i][j]
            return triangle[i][j] + min(best(i + 1, j), best(i + 1, j + 1))

        return best(0, 0)

Complexity: O(n²) time and space (one entry per cell, plus recursion stack).

Approach 3 — Tabulated bottom-up (2-D)

The insight: build a dp grid where dp[i][j] is the min path sum from (i, j) to the bottom. Seed the last row from the triangle, then fill upward.

class Solution:
    def minimumTotal(self, triangle: list[list[int]]) -> int:
        n = len(triangle)
        dp = [row[:] for row in triangle]      # copy so we don't mutate input
        for i in range(n - 2, -1, -1):
            for j in range(i + 1):
                dp[i][j] += min(dp[i + 1][j], dp[i + 1][j + 1])
        return dp[0][0]

Complexity: O(n²) time, O(n²) space.

Approach 4 — Space-optimized 1-D (the intended solution)

The insight: filling bottom-up, row i reads only row i+1. Keep a single array dp of length n initialized to the bottom row; each higher row overwrites it in place, left to right (each dp[j] uses the old dp[j] and dp[j+1], both still valid before this cell is written).

class Solution:
    def minimumTotal(self, triangle: list[list[int]]) -> int:
        dp = triangle[-1][:]                    # start from the bottom row
        for i in range(len(triangle) - 2, -1, -1):
            for j in range(i + 1):
                dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
        return dp[0]

Walkthrough (triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]):

start dp = [4,1,8,3]
row [6,5,7]: dp[0]=6+min(4,1)=7, dp[1]=5+min(1,8)=6, dp[2]=7+min(8,3)=10 → dp=[7,6,10,3]
row [3,4]: dp[0]=3+min(7,6)=9, dp[1]=4+min(6,10)=10 → dp=[9,10,...]
row [2]: dp[0]=2+min(9,10)=11 → dp[0]=11. ✓

Complexity: O(n²) time, O(n) space — meeting the follow-up.

Common pitfalls

Going top-down in the tabulation and mishandling the edges (the leftmost and rightmost cells of each row have only one valid parent above). Bottom-up sidesteps this entirely — every interior cell has both children present.
Overwriting the 1-D array right-to-left, which corrupts the dp[j+1] you still need; go left-to-right in the bottom-up scheme above.
Mutating the input triangle in place when the caller may reuse it — copy the bottom row.
Assuming values are non-negative: entries can be negative, so a greedy “always pick the smaller next cell” fails; only the DP is correct.

Pattern takeaway

Grid/triangle path-sum problems reduce to “this cell’s best = its value + best of the cells it can reach.” Compute it bottom-up so every dependency is ready and the edge cases vanish, then compress the DP table to a single row whenever each row only reads its immediate neighbor row — the standard 2-D-to-1-D space optimization.