LeetCode 120 - Triangle

The problem gives us a triangular array of integers and asks us to compute the minimum path sum from the top row to the bottom row. The input is a two-dimensional array called triangle, where: - The first row contains exactly one number.

leetcodemediumarraydynamic-programming

LeetCode Problem 120

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem gives us a triangular array of integers and asks us to compute the minimum path sum from the top row to the bottom row.

The input is a two-dimensional array called triangle, where:

  • The first row contains exactly one number.
  • Each subsequent row contains one more element than the previous row.
  • From any position in a row, we are allowed to move only to one of two adjacent positions in the next row.

If we are currently at index i in row r, then in row r + 1 we may move to:

  • index i
  • index i + 1

Our goal is to choose a path from the top of the triangle to the bottom such that the sum of all chosen numbers is as small as possible.

For example, consider:

   2
  3 4
 6 5 7
4 1 8 3

Starting at 2, we can move down row by row while respecting adjacency rules. The optimal path is:

2 → 3 → 5 → 1

which produces:

2 + 3 + 5 + 1 = 11

The constraints are important:

  • The triangle can have up to 200 rows.
  • Values may be negative, ranging from -10^4 to 10^4.

Since the number of rows can be fairly large, a brute-force search through every possible path quickly becomes too expensive. Also, because negative numbers are allowed, we cannot rely on greedy decisions such as always taking the smaller immediate child, since a locally smaller choice may lead to a much larger total later.

Several edge cases are important:

  • A triangle with only one row, such as [[-10]], where the answer is simply that value.
  • Triangles containing negative numbers, where the optimal path may intentionally include a larger immediate value to achieve a smaller total later.
  • Large triangles, where exponential recursion becomes impractical.
  • Cases where multiple paths produce the same minimum sum, where any valid minimum should still be computed correctly.

Approaches

Brute Force Approach

A straightforward way to solve this problem is to explore every possible path from the top to the bottom using recursion.

At each position (row, col), we have exactly two choices:

  1. Move to (row + 1, col)
  2. Move to (row + 1, col + 1)

We recursively compute the minimum path sum for both options and return:

triangle[row][col] + min(left_path, right_path)

This approach is correct because it evaluates all valid paths and chooses the minimum total among them.

However, the problem is that the number of paths grows exponentially. Since every row introduces two choices, the recursion tree becomes extremely large.

For a triangle with n rows, the time complexity becomes approximately O(2^n).

This is far too slow for n = 200.

Key Insight

The important observation is that many subproblems repeat.

For example, suppose two different paths both arrive at the same cell. From that cell onward, the minimum remaining path sum is always identical. Recomputing it repeatedly is wasteful.

This makes the problem a natural fit for dynamic programming.

Instead of exploring paths repeatedly, we can compute the minimum cost from the bottom upward.

The key recurrence is:

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

Here:

  • dp[col] represents the minimum path sum from the current position downward.
  • dp[col] and dp[col + 1] store results from the row below.

By starting from the bottom row and moving upward, we reuse already-computed optimal subproblems.

Even better, we only need one array of size n (number of rows), which satisfies the follow-up requirement of O(n) extra space.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Recursively explores every possible path
Optimal Dynamic Programming O(n²) O(n) Bottom-up DP with a single array

Algorithm Walkthrough

Optimal Bottom-Up Dynamic Programming

  1. Create a dynamic programming array initialized with the values of the last row.

The last row already represents the minimum cost to reach the bottom from itself, because there are no further moves.

Example:

Triangle:
   2
  3 4
 6 5 7
4 1 8 3

Initial dp:
[4, 1, 8, 3]
  1. Process rows from the second-last row upward.

For each element, compute:

current value + minimum of the two reachable children
  1. Update the DP array in place.

For 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

Updated:

[7, 6, 10, 3]
  1. Continue upward until the top row.

Row [3,4]:

dp[0] = 3 + min(7,6) = 9
dp[1] = 4 + min(6,10) = 10

Updated:

[9, 10, 10, 3]
  1. Process the top row.
dp[0] = 2 + min(9,10) = 11
  1. Return dp[0].

After processing all rows, the first position contains the minimum path sum from top to bottom.

Why it works

The algorithm works because of the optimal substructure property. The minimum path sum from a cell depends only on the minimum path sums of its two reachable children.

When processing a row, the DP array already contains the correct minimum costs for the row below. Therefore, every update computes the correct optimal value for the current row. By repeatedly moving upward, the top cell eventually contains the globally minimum path sum.

Python Solution

from typing import List

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

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

        return dp[0]

The implementation begins by copying the last row into dp. This serves as the base case because the minimum cost from the bottom row to itself is simply its own value.

Next, we iterate upward from the second-last row to the first row. For every position, we calculate the current value plus the smaller of its two reachable children in the row below.

The important detail is that the update happens in place. Since we process left to right, dp[col] and dp[col + 1] still represent the previous row's values when needed.

After all rows are processed, dp[0] stores the minimum path sum from the top to the bottom.

Go Solution

func minimumTotal(triangle [][]int) int {
	dp := make([]int, len(triangle[len(triangle)-1]))
	copy(dp, triangle[len(triangle)-1])

	for row := len(triangle) - 2; row >= 0; row-- {
		for col := 0; col < len(triangle[row]); col++ {
			if dp[col] < dp[col+1] {
				dp[col] = triangle[row][col] + dp[col]
			} else {
				dp[col] = triangle[row][col] + dp[col+1]
			}
		}
	}

	return dp[0]
}

The Go implementation follows the same bottom-up dynamic programming strategy.

Since slices are reference-based, we explicitly create a new slice and use copy() to avoid modifying the original last row in triangle.

Instead of using min(), Go uses a simple conditional comparison because there is no built-in integer minimum function.

Integer overflow is not a concern here because the maximum possible sum remains safely within Go's integer range.

Worked Examples

Example 1

Input:

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

Initial state:

Step Row Being Processed DP State
Initial [4,1,8,3] [4,1,8,3]

Process row [6,5,7]:

Index Calculation Result
0 6 + min(4,1) 7
1 5 + min(1,8) 6
2 7 + min(8,3) 10

Updated DP:

[7, 6, 10, 3]

Process row [3,4]:

Index Calculation Result
0 3 + min(7,6) 9
1 4 + min(6,10) 10

Updated DP:

[9, 10, 10, 3]

Process row [2]:

Index Calculation Result
0 2 + min(9,10) 11

Final DP:

[11, 10, 10, 3]

Answer:

11

Example 2

Input:

[[-10]]

Initial DP:

[-10]

There are no additional rows to process.

Return:

-10

Complexity Analysis

Measure Complexity Explanation
Time O(n²) We visit every element in the triangle exactly once
Space O(n) We store only one DP array of size equal to the number of rows

Although the triangle contains roughly n² elements for n rows, each element is processed exactly one time. Therefore, the running time is proportional to the total number of cells in the triangle.

The extra memory usage is only one array storing the current DP state, which satisfies the follow-up requirement of O(n) space.

Test Cases

solution = Solution()

assert solution.minimumTotal([[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]) == 11  # Example case
assert solution.minimumTotal([[-10]]) == -10  # Single element triangle
assert solution.minimumTotal([[1], [2, 3]]) == 3  # Simple two-row triangle
assert solution.minimumTotal([[1], [1, 1], [1, 1, 1]]) == 3  # Uniform values
assert solution.minimumTotal([[5], [-2, -3]]) == 2  # Negative values
assert solution.minimumTotal([[1], [2, 1], [1, 1, 1]]) == 3  # Multiple optimal paths
assert solution.minimumTotal([[10000]]) == 10000  # Maximum positive value
assert solution.minimumTotal([[-10000]]) == -10000  # Minimum negative value
assert solution.minimumTotal([[1], [2, 3], [3, 6, 1], [7, 2, 8, 4]]) == 10  # Mixed path choices
Test Why
[[2],[3,4],[6,5,7],[4,1,8,3]] Validates the main example
[[-10]] Tests single-row triangle
[[1],[2,3]] Smallest non-trivial triangle
Uniform values Ensures repeated values work correctly
Negative values Verifies handling of negative numbers
Multiple optimal paths Ensures minimum is computed consistently
Maximum positive value Boundary value test
Minimum negative value Negative boundary test
Mixed path choices Validates non-greedy optimal selection

Edge Cases

Single Row Triangle

A triangle containing only one row is the smallest valid input. A naive implementation might accidentally assume at least one transition between rows exists.

For example:

[[-10]]

The implementation handles this naturally because the DP array is initialized with the last row, and the outer loop never executes. The result is simply dp[0].

Negative Numbers

Negative values make greedy strategies unreliable. Choosing the smaller immediate child may not lead to the globally optimal solution.

Example:

[
 [5],
 [-2, -3]
]

The algorithm correctly evaluates both reachable children using dynamic programming and chooses the true minimum total.

Large Triangles

With up to 200 rows, a brute-force recursive solution would become infeasible because of exponential growth in possible paths.

The bottom-up DP solution processes every element exactly once and uses only a single array, making it efficient enough even for the largest valid inputs.