120. Triangle - Explanation

Description

You are 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 minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11

Example 2:

Input: triangle = [[-1]]

Output: -1

Constraints:

1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-10,000 <= triangle[i][j] <= 10,000

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

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

Intuition

Starting from the top of the triangle, at each position we can move either directly down or diagonally down-right. We want to find the path from top to bottom with the minimum sum.

This naturally leads to a recursive approach: from position (row, col), we add the current value and recurse to both possible next positions, taking the minimum result. The base case is reaching past the bottom row, where we return 0.

Algorithm

Define a recursive function dfs(row, col) that returns the minimum path sum from that position to the bottom.
Base case: if row exceeds the triangle height, return 0.
Return the current cell value plus the minimum of dfs(row + 1, col) and dfs(row + 1, col + 1).
Start the recursion from position (0, 0).

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        def dfs(row, col):
            if row >= len(triangle):
                return 0
            return triangle[row][col] + min(dfs(row + 1, col), dfs(row + 1, col + 1))

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$ for recursion stack.

2. Dynamic Programming (Top-Down)

Intuition

The recursive solution recomputes the same subproblems many times. For example, position (2, 1) might be reached from both (1, 0) and (1, 1). We can use memoization to store results once computed.

By caching the minimum path sum from each position, we ensure each subproblem is solved only once. This transforms the exponential time complexity into polynomial.

Algorithm

Create a memoization table memo initialized with infinity to mark unvisited cells.
Define dfs(row, col) that first checks the memo cache before computing.
If cached, return the stored value immediately.
Otherwise, compute the result recursively, store it in memo, and return it.
Start from (0, 0) and return the result.

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        memo = [[0] * len(triangle[r]) for r in range(len(triangle))]
        INF = float("inf")
        for r in range(len(triangle)):
            for c in range(len(triangle[r])):
                memo[r][c] = INF

        def dfs(row, col):
            if row >= len(triangle):
                return 0
            if memo[row][col] != INF:
                return memo[row][col]

            memo[row][col] = triangle[row][col] + min(dfs(row + 1, col), dfs(row + 1, col + 1))
            return memo[row][col]

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

3. Dynamic Programming (Bottom-Up)

Intuition

Instead of recursing from top to bottom, we can build the solution from the bottom up. Starting from the last row (where the values are the path sums themselves), we work upward. At each cell, we add the minimum of the two cells below it.

This eliminates recursion overhead and naturally fills the dp table in the correct order. By the time we reach the top, dp[0][0] contains the minimum path sum.

Algorithm

Create a dp table with the same shape as the triangle.
Initialize the bottom row of dp with the bottom row of the triangle.
Iterate from the second-to-last row up to the first row.
For each cell, set dp[row][col] = triangle[row][col] + min(dp[row+1][col], dp[row+1][col+1]).
Return dp[0][0].

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        dp = [[0] * len(triangle[row]) for row in range(n)]
        dp[-1] = triangle[-1][:]

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

        return dp[0][0]

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

4. Dynamic Programming (Space Optimized) - I

Intuition

When building top-down, we only need the previous row to compute the current row. We can use a single array that grows as we move down the triangle, updating values as we go.

The tricky part is handling the edges correctly. The leftmost element of each row can only come from the leftmost element above. The rightmost can only come from the rightmost above. Middle elements take the minimum of their two parents.

Algorithm

Initialize dp with the first row of the triangle.
For each subsequent row, create a new nxtDp array of appropriate size.
Set the first element as dp[0] + triangle[row][0].
For middle elements, take triangle[row][col] + min(dp[col], dp[col-1]).
Set the last element as dp[last] + triangle[row][last].
Replace dp with nxtDp.
Return the minimum value in the final dp array.

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

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

        return min(dp)

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$ extra space.

5. Dynamic Programming (Space Optimized) - II

Intuition

Working bottom-up with space optimization is cleaner because we process elements left to right, and each cell only depends on cells to its right in the row below. This means we can safely overwrite values as we go without corrupting data we still need.

We start with the bottom row and repeatedly update each position with the minimum path sum from that point down. The final answer ends up in dp[0].

Algorithm

Initialize dp as a copy of the bottom row.
Iterate from the second-to-last row up to the first.
For each position in the current row, update dp[col] = triangle[row][col] + min(dp[col], dp[col+1]).
Since we process left to right and dp[col+1] is accessed before dp[col] is overwritten, no data is lost.
Return dp[0] after processing all rows.

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]

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$ extra space.

6. Dynamic Programming (In-Place)

Intuition

If we are allowed to modify the input triangle, we can skip creating a separate DP array entirely. We use the triangle itself to store intermediate results, applying the same bottom-up logic.

This approach uses constant extra space but modifies the input data. Each cell in the triangle gets replaced with the minimum path sum from that cell to the bottom.

Algorithm

Iterate from the second-to-last row up to the first.
For each cell, update triangle[row][col] += min(triangle[row+1][col], triangle[row+1][col+1]).
The update modifies the current cell based on the two cells directly below it.
After all iterations, triangle[0][0] contains the minimum path sum.
Return triangle[0][0].

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        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]

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$ extra space.

Common Pitfalls

Using Top-Down DP Without Tracking the Minimum at the Bottom

When using top-down dynamic programming, the minimum path sum ends up at one of the cells in the last row, not necessarily at a fixed position. A common mistake is to return dp[n-1][0] or dp[n-1][n-1] instead of finding the minimum across the entire bottom row. The bottom-up approach avoids this by naturally propagating the answer to dp[0][0].

Incorrect Index Handling for Adjacent Cells

In the triangle, a cell at position (row, col) can only move to (row+1, col) or (row+1, col+1). A common error is to treat this like a standard grid where you can move to col-1 as well. Since each row has exactly row+1 elements, the valid adjacent indices are strictly col and col+1 in the next row.

Forgetting to Handle Single-Element Triangles

When the triangle has only one row with a single element, some implementations may fail if they assume there are at least two rows. Always ensure your base case or loop bounds correctly handle the edge case where n == 1, returning the single element as the answer.