Triangle

Difficulty: Medium
Topics: Array, Dynamic Programming
Link: https://leetcode.com/problems/triangle/

Problem Description

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

Example 1:


Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Example 2:


Input: triangle = [[-10]]
Output: -10

Constraints:

1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-104 <= triangle[i][j] <= 104

Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?

Solution

1. Problem Deconstruction

Rewrite the Problem

Technical Version

Given a triangular array triangle of size ( n ) (number of rows), where each row ( i ) (0-indexed) contains ( i+1 ) integers. A valid path from the top to the bottom is a sequence of indices ((0, j_0), (1, j_1), \dots, (n-1, j_{n-1})) such that:

( j_0 = 0 ) (the top element).
For each step ( k ) from 0 to ( n-2 ), ( j_{k+1} \in { j_k, j_k + 1 } ) (adjacent indices in the next row).

The path sum is ( \sum_{i=0}^{n-1} \text{triangle}[i][j_i] ). The objective is to find the minimum possible path sum over all valid paths.

This can be viewed as a shortest-path problem on a directed acyclic graph (DAG) where nodes are positions ((i, j)) and edges connect to ((i+1, j)) and ((i+1, j+1)), with edge weights equal to the value at the child node (or equivalently, node weights). The goal is to minimize the cumulative weight from the source node ((0,0)) to any sink node in row ( n-1 ).

Beginner Version

Imagine a pyramid of numbers. You start at the top number. On each step, you can move directly down to the number immediately below, or down and slightly to the right to the number below and to the right. You want to find a path from the top to the bottom that gives the smallest total sum of numbers you pass through. The pyramid’s shape means each row has one more number than the row above.

Mathematical Version

Let ( T ) be a triangular matrix with rows ( i = 0, 1, \dots, n-1 ) and columns ( j = 0, 1, \dots, i ). Define a path ( P = (j_0, j_1, \dots, j_{n-1}) ) satisfying:

( j_0 = 0 )
( j_{i+1} \in { j_i, j_i + 1 } ) for ( i = 0, \dots, n-2 ).

We seek: [ \min_{P} \sum_{i=0}^{n-1} T[i][j_i] ]

Equivalently, define ( \text{dp}(i, j) ) as the minimum path sum to reach position ((i, j)). The recurrence is: [ \text{dp}(i, j) = T[i][j] + \begin{cases} \text{dp}(i-1, 0) & \text{if } j = 0 \ \text{dp}(i-1, j-1) & \text{if } j = i \ \min(\text{dp}(i-1, j-1), \text{dp}(i-1, j)) & \text{otherwise} \end{cases} ] with base case ( \text{dp}(0, 0) = T[0][0] ). The answer is ( \min_{j} \text{dp}(n-1, j) ).

Constraint Analysis

1 <= triangle.length <= 200
The number of rows ( n ) is at most 200, so the total number of elements is ( \frac{n(n+1)}{2} \leq 20,100 ). This allows ( O(n^2) ) time algorithms, but also motivates space optimization since ( O(n^2) ) memory (∼160 KB for integers) is acceptable but can be improved.
triangle[0].length == 1
Ensures the triangle starts with a single element, simplifying the problem’s initialization. Implicitly defines the starting point as triangle[0][0].
triangle[i].length == triangle[i - 1].length + 1
Guarantees the triangular structure: each row has one more element than the previous. This invariant ensures that the adjacency condition is well-defined (no missing indices). It also implies that the last row has ( n ) elements.
-10^4 <= triangle[i][j] <= 10^4
Values can be negative, so the minimum path sum may be negative. This prevents greedy approaches that assume non-negative weights. The absolute sum is bounded by ( n \times 10^4 \leq 2 \times 10^6 ), which fits within 32-bit signed integers, avoiding overflow concerns.

Hidden Edge Cases:

Single-row triangle: The answer is simply the top element.
All negative values: The path sum will be highly negative; the algorithm must correctly propagate negatives.
Mixed signs: The optimal path might sacrifice a locally larger value for a globally smaller sum.
Large n (200): Tests the efficiency of the algorithm; exponential approaches will fail.
Boundary elements: The first and last column of each row have only one parent, requiring special handling in DP transitions.

2. Intuition Scaffolding

Generate 3 Analogies

Real-World Metaphor: Skiing Down a Mountain
Imagine a triangular ski slope with numbered gates. Each gate has a penalty (positive) or reward (negative). Starting at the top gate, you can ski directly to the gate below or below and to the right. Your goal is to minimize the total penalty (or maximize reward). This mirrors the path choices and sum minimization.
Gaming Analogy: Dungeon Crawler
In a pyramid-shaped dungeon, each room contains a monster with a certain strength. You start at the top room and must descend to the bottom floor, choosing adjacent rooms. You want to minimize the total strength of monsters encountered. This reflects the adjacency constraint and optimization goal.
Math Analogy: Trellis Diagram in Viterbi Algorithm
The triangle can be seen as a trellis graph where each node has two incoming edges (except boundaries). The minimum path sum is analogous to the Viterbi algorithm’s maximum likelihood path, but with minimization instead of maximization. This connects to dynamic programming on DAGs.

Common Pitfalls Section

Greedy Selection (Pick Min Adjacent at Each Step)
Choosing the smaller of the two reachable numbers at each step ignores future rows.
Counterexample:
```
  1
 2 3
1 0 100
```
Greedy: ( 1 \to 2 \to 0 = 3 ). Optimal: ( 1 \to 3 \to 0 = 4 ) (worse). Actually, need a case where greedy is suboptimal.
Better counterexample:
```
  1
 2 10
100 1 2
```
Greedy: ( 1 \to 2 \to 1 = 4 ). Optimal: ( 1 \to 10 \to 1 = 12 ) (worse again). Let’s construct:
```
  -1
  2  3
 1 -1 -4
```
Greedy: (-1 \to 2 \to -1 = 0). Optimal: (-1 \to 3 \to -4 = -2). So greedy fails.
Global Minimum Per Row
Selecting the smallest number in each row independently violates adjacency.
Example: The smallest in row 2 might not be reachable from the smallest in row 1.
Dijkstra’s Algorithm
While correct, it is overkill (( O(E \log V) )) for a DAG with a simple topological order. DP is more efficient and simpler.
Exhaustive Recursion Without Memoization
Exploring all ( 2^{n-1} ) paths is infeasible for ( n = 200 ).
Incorrect DP Initialization/Boundaries
Forgetting to handle the first and last columns specially leads to out-of-bounds access or incorrect sums.

3. Approach Encyclopedia

Brute Force (Recursive Exploration)

Pseudocode:

def min_path(triangle, i, j):
    # Base case: bottom row
    if i == len(triangle) - 1:
        return triangle[i][j]
    # Recurse on both possible children
    left = min_path(triangle, i+1, j)
    right = min_path(triangle, i+1, j+1)
    return triangle[i][j] + min(left, right)

# Call:
min_path(triangle, 0, 0)

Complexity Proof:

Time: Each call spawns two recursive calls, leading to a binary tree of depth ( n ). Total calls: ( 2^n - 1 ), so ( O(2^n) ).
Space: Recursion stack depth is ( n ), so ( O(n) ).

Visualization:

Recursion tree for n=3:
        (0,0)
       /      \
    (1,0)    (1,1)
    /   \    /   \
 (2,0)(2,1)(2,1)(2,2)

Memoization (Top-Down DP)

Pseudocode:

def minimumTotal(triangle):
    n = len(triangle)
    memo = [[None] * n for _ in range(n)]  # memo[i][j] stores min path sum to (i,j)
    
    def dfs(i, j):
        if i == n - 1:
            return triangle[i][j]
        if memo[i][j] is not None:
            return memo[i][j]
        left = dfs(i+1, j)
        right = dfs(i+1, j+1)
        memo[i][j] = triangle[i][j] + min(left, right)
        return memo[i][j]
    
    return dfs(0, 0)

Complexity Proof:

Time: Each of the ( O(n^2) ) states is computed once, and each state does constant work, so ( O(n^2) ).
Space: ( O(n^2) ) for the memo table plus ( O(n) ) recursion stack.

Visualization:

Memo table fill order (example n=4):
Row 3: [4,1,8,3] (base)
Row 2: [6+min(4,1), 5+min(1,8), 7+min(8,3)] = [7,6,10]
Row 1: [3+min(7,6), 4+min(6,10)] = [9,10]
Row 0: [2+min(9,10)] = [11]

Bottom-Up DP (2D Array)

Pseudocode:

def minimumTotal(triangle):
    n = len(triangle)
    dp = [[0] * n for _ in range(n)]
    dp[0][0] = triangle[0][0]
    for i in range(1, n):
        for j in range(i+1):
            if j == 0:
                dp[i][j] = triangle[i][j] + dp[i-1][j]
            elif j == i:
                dp[i][j] = triangle[i][j] + dp[i-1][j-1]
            else:
                dp[i][j] = triangle[i][j] + min(dp[i-1][j-1], dp[i-1][j])
    return min(dp[n-1])

Complexity Proof:

Time: Two nested loops over ( O(n^2) ) elements, each constant work: ( O(n^2) ).
Space: ( O(n^2) ) for the DP table.

Visualization:

DP table for example:
Row 0: [2, 0, 0, 0]
Row 1: [5, 6, 0, 0]
Row 2: [11,10,13,0]
Row 3: [15,11,18,16] -> min=11

Bottom-Up DP with O(n) Space (Optimal)

Insight: Only the previous row is needed to compute the current row. We can use a single array and update it in reverse order to avoid overwriting needed values.

Pseudocode:

def minimumTotal(triangle):
    n = len(triangle)
    dp = [0] * n
    dp[0] = triangle[0][0]
    for i in range(1, n):
        # Update from right to left
        dp[i] = triangle[i][i] + dp[i-1]          # Rightmost element
        for j in range(i-1, 0, -1):              # Middle elements
            dp[j] = triangle[i][j] + min(dp[j-1], dp[j])
        dp[0] = triangle[i][0] + dp[0]           # Leftmost element
    return min(dp)

Complexity Proof:

Time: Still ( O(n^2) ) because of the nested loop over all elements.
Space: ( O(n) ) for the dp array.

Visualization:

Step-by-step for example:
Initial: dp = [2,0,0,0]
Row 1: update dp[1]=4+2=6, then dp[0]=3+2=5 → [5,6,0,0]
Row 2: update dp[2]=7+6=13, then dp[1]=5+min(5,6)=10, then dp[0]=6+5=11 → [11,10,13,0]
Row 3: update dp[3]=3+13=16, then dp[2]=8+min(10,13)=18, then dp[1]=1+min(11,10)=11, then dp[0]=4+11=15 → [15,11,18,16]
min=11

4. Code Deep Dive

Line-by-Line Annotations (Optimal Solution)

def minimumTotal(triangle):
    n = len(triangle)                     # 1. Number of rows
    dp = [0] * n                          # 2. DP array: min sum to current row's columns
    dp[0] = triangle[0][0]                # 3. Base case: top element
    
    for i in range(1, n):                 # 4. Iterate over rows 1 to n-1
        # 5. Handle rightmost column (j = i)
        #    Only one parent: previous row's j-1 (dp[i-1] still old because we go right-to-left)
        dp[i] = triangle[i][i] + dp[i-1]
        
        # 6. Handle middle columns (j = i-1 down to 1)
        #    Update in reverse to preserve previous row's values:
        #    At position j, dp[j] and dp[j-1] are still from previous row.
        for j in range(i-1, 0, -1):
            dp[j] = triangle[i][j] + min(dp[j-1], dp[j])
        
        # 7. Handle leftmost column (j = 0)
        #    Only one parent: previous row's j=0 (dp[0] still old)
        dp[0] = triangle[i][0] + dp[0]
    
    return min(dp)                        # 8. Minimum of last row

Edge Case Handling

Single row (n=1): Loop doesn’t run, dp[0] is returned directly. Works.
Negative numbers: The recurrence correctly accumulates negatives because min is used.
Large n (200): The ( O(n^2) ) time is fine; space is ( O(n) ), efficient.
Example 1: As visualized above, returns 11.
Example 2: triangle = [[-10]] returns -10.

5. Complexity War Room

Hardware-Aware Analysis

Memory: For ( n = 200 ), the ( O(n) ) DP array uses ( 200 \times 4 ) bytes = 800 bytes, fitting in L1 cache (typically 32–64 KB). Even the ( O(n^2) ) table (40,000 integers) uses ~160 KB, fitting in L2/L3 cache. This ensures cache-friendly performance.
CPU: ( O(n^2) = 40,000 ) operations is trivial on modern CPUs (µs to ms range).

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute Force Recursion	( O(2^n) )	( O(n) )	9/10 (simple)	❌ Fails for n>30
Memoization (Top-Down)	( O(n^2) )	( O(n^2) )	8/10 (clear recursion)	✅ Acceptable
Bottom-Up 2D DP	( O(n^2) )	( O(n^2) )	9/10 (straightforward)	✅ Good
Bottom-Up 1D DP (optimal)	( O(n^2) )	( O(n) )	7/10 (requires careful indexing)	✅ Best (meets follow-up)

6. Pro Mode Extras

Variants Section

Maximum Path Sum in Triangle
Replace min with max in the recurrence.
Triangle with More Moves
If you can move to ((i+1, j-1)), ((i+1, j)), ((i+1, j+1)) (with bounds), the DP updates need three parents.
Minimum Path Sum in Square Matrix (LeetCode 931)
Similar but on an ( n \times n ) matrix, moves: down-left, down, down-right. Solution uses 1D DP with careful ordering.
Multiple Transactions (LeetCode 123)
If you could split the path into two separate transactions? Not directly analogous, but dynamic programming with state (row, transactions used) could be applied.
Starting from Any Row
If you can start from any element in the top row, initialize dp with the first row values.
Output the Path Itself
Store predecessors in DP to reconstruct the chosen indices.

Interview Cheat Sheet

First Mention Complexity: Always state time/space upfront.
Start Simple: Describe brute force, then optimize.
Visual Aid: Draw the triangle and DP table on the board.
Space Optimization: Explain why reverse iteration preserves previous row.
Test Small Cases: Verify with the given examples.
Edge Cases: Single row, negatives, boundaries.
Follow-Up Ready: Know the ( O(n) ) space solution.

#120 - Triangle

Triangle

Problem Description

Solution

1. Problem Deconstruction

Rewrite the Problem

Technical Version

Beginner Version

Mathematical Version

Constraint Analysis

2. Intuition Scaffolding

Generate 3 Analogies

Common Pitfalls Section

3. Approach Encyclopedia

Brute Force (Recursive Exploration)

Memoization (Top-Down DP)

Bottom-Up DP (2D Array)

Bottom-Up DP with O(n) Space (Optimal)

4. Code Deep Dive

Line-by-Line Annotations (Optimal Solution)

Edge Case Handling

5. Complexity War Room

Hardware-Aware Analysis

Industry Comparison Table

6. Pro Mode Extras

Variants Section

Interview Cheat Sheet