Triangle Solution | SkillFlow

Problem

Given a triangle (a nested array where row i contains exactly i + 1 numbers), find the minimum sum path from the top element down to the bottom row. At each step you may move to the same index or the next index in the row below — there is no moving left or diagonally backward.

Input: [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The path 2 → 3 → 5 → 1 sums to 11, which is the smallest possible.

A greedy counter-example: the triangle [[-1],[2,3],[1,-1,-3]] has minimum path −1 → 3 → −3 = −1, not −1 → 2 → −1 = 0 — showing that locally smaller neighbors don't always win.

Intuition

Every root-to-bottom path touches exactly one cell per row, and the only choices at each step are "straight down" or "diagonal right." The best total cost from any cell depends only on the best costs of the two cells reachable below it — a clean recursive sub-structure. Building the answer from the bottom eliminates the need to track paths explicitly.

Approach 1 — Top-Down with Memoization

Start at the apex and recurse downward, caching each (row, col) result so it is computed at most once.

Define min_path(row, col) as the minimum sum achievable starting at that cell.
Base case: the last row has no children, so return the cell value directly.
Recurse to the two reachable children — same column and column + 1 in the next row.
Cache the result before returning so overlapping sub-problems are answered in O(1).
The answer is min_path(0, 0).

1from functools import lru_cache
2
3def minimumTotal(triangle):
4    n = len(triangle)
5
6    @lru_cache(maxsize=None)
7    def min_path(row, col):
8        if row == n - 1:
9            return triangle[row][col]
10        # Only two legal moves: same col or col+1 in the next row
11        return triangle[row][col] + min(
12            min_path(row + 1, col),
13            min_path(row + 1, col + 1)
14        )
15
16    return min_path(0, 0)

Time: O(n²) — each of the n(n+1)/2 cells is visited and stored exactly once.
Space: O(n²) — the memo table holds one entry per cell plus O(n) recursion stack depth.

Approach 2 — Bottom-Up DP (Space-Optimized)

Copy the last row into a 1D array and propagate minimum costs upward row by row, reusing the same array.

Initialize dp as a copy of the bottom row — these are the trivial single-cell path sums.
For each row from n - 2 down to 0, iterate columns 0 through row (inclusive).
Overwrite dp[col] with triangle[row][col] + min(dp[col], dp[col + 1]).
Left-to-right iteration is safe: dp[col + 1] still holds the previous row's value when dp[col] is computed.
After all rows, dp[0] is the answer.

1def minimumTotal(triangle):
2    dp = triangle[-1][:]  # copy last row; these are the base-case path costs
3
4    for row in range(len(triangle) - 2, -1, -1):
5        for col in range(len(triangle[row])):
6            # dp[col+1] hasn't been updated yet this iteration, so it's safe to read
7            dp[col] = triangle[row][col] + min(dp[col], dp[col + 1])
8
9    return dp[0]

Time: O(n²) — every cell is processed once.
Space: O(n) — a single array of size n replaces the full 2D memo table.

Complexity Summary

Approach	Time	Space	When to use
Top-Down Memoization	O(n²)	O(n²)	Debugging or learning — the recursion mirrors the problem statement directly
Bottom-Up Space-Optimized	O(n²)	O(n)	Production — iterative, minimal memory, no stack-overflow risk

Common Mistakes

Greedy neighbor selection: Always picking the smaller adjacent value produces a locally optimal step but not globally — a cheap cell in one row may lead to expensive cells below.
Forgetting that adjacency is restricted: From (row, col) you can only move to (row+1, col) or (row+1, col+1). Moving to (row+1, col-1) is illegal, unlike standard 2D grid problems.
Seeding dp with zeros instead of the last row: Starting with dp = [0] * n gives incorrect base costs — the correct seed is a copy of the last row's actual values.
Off-by-one on the row loop: The outer loop must start at n - 2, not n - 1. Row n - 1 is already the base case; re-processing it corrupts dp.
Recursive approach without caching: Without memoization each cell is recomputed up to 2^(n-1) times — exponential cost. Even a 30-row triangle would trigger over a billion calls.

Triangle — Solution