AlgoMaster Logo

Triangle

mediumFrequency7 min readUpdated June 23, 2026

Understanding the Problem

We are given a triangle of numbers, and we need to find a path from the top to the bottom that gives the smallest possible sum. From any position in the triangle, we can only move to the element directly below or to the element one position to the right on the row below. So this is not about picking the global minimum from each row, it is about finding a connected path that minimizes the total sum.

A greedy approach (always pick the smaller neighbor below) does not work. Taking a larger value now can open up a cheaper path later. For example, with rows [1], [2, 3], [100, 100, 1], greedy moves 1 -> 2 (the smaller child) and is then forced into a 100 for a total of 103, while moving 1 -> 3 reaches the bottom-right 1 for a total of 5. This is a signal for dynamic programming: the problem has optimal substructure (the best path through a cell depends on the best path from that cell downward) combined with overlapping subproblems (multiple paths from above converge on the same cell).

Key Constraints:

  • 1 <= triangle.length <= 200 --> The triangle has at most 200 rows, about 20,000 elements total. An O(n^2) solution where n is the number of rows is well within limits.
  • -10^4 <= triangle[i][j] <= 10^4 --> Values can be negative, which rules out any approach that assumes all values are non-negative. With at most 200 rows and values bounded by 10^4, the largest possible sum is 200 10^4 = 2 10^6, far below the 32-bit integer limit, so a plain int accumulator never overflows.
  • triangle[i].length == triangle[i - 1].length + 1 --> The triangle is well-formed. Row i has exactly i + 1 elements, so the adjacency rule always leads to valid positions.

Approach 1: Recursion (Brute Force)

Intuition

Think about the problem top-down. Starting at the apex of the triangle, at each cell we have two choices: go to the adjacent element below-left (same index on the next row) or below-right (index + 1 on the next row). We want the path that gives the smallest total sum.

So for each cell (row, col), the minimum path sum from that cell to the bottom is:

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

The base case is the last row, where the minimum path sum is the cell's own value. This is correct, but it explores every possible path through the triangle. From the top, there are 2 choices at each of the n - 1 levels, leading to 2^(n-1) paths.

Algorithm

  1. Define a recursive function minPath(row, col) that returns the minimum path sum from cell (row, col) to the bottom of the triangle.
  2. Base case: if row is the last row, return triangle[row][col].
  3. Recursively compute the minimum path sum from (row + 1, col) and (row + 1, col + 1).
  4. Return triangle[row][col] plus the smaller of those two results.
  5. Call minPath(0, 0) for the answer.

Example Walkthrough

Input:

0
0
2
1
3
4
2
6
5
7
3
4
1
8
3
triangle

The recursion explores all paths: 2->3->6->4, 2->3->6->1, 2->3->5->1, 2->3->5->8, 2->4->5->1, 2->4->5->8, 2->4->7->8, 2->4->7->3. The minimum is 2+3+5+1 = 11.

11
result

Code

The recursion recomputes the same cells repeatedly. Cell (2, 1), for instance, is reached from both (1, 0) and (1, 1). Caching each result after the first computation removes that repeated work.

Approach 2: Top-Down DP (Memoization)

Intuition

The brute force recurrence is correct; the problem is that it recomputes the same subproblems many times. A memo table that caches the result of minPath(row, col) after the first call lets every subsequent call with the same (row, col) return in O(1).

The triangle has 1 + 2 + ... + n = n(n+1)/2 cells, so once every cell is computed once, the work is done. This brings the time complexity from exponential down to O(n^2).

Algorithm

  1. Create a 2D memo table (or dictionary) to store computed results.
  2. Define minPath(row, col): if the result is cached, return it. Base case: last row returns its value. Otherwise compute triangle[row][col] + min(minPath(row + 1, col), minPath(row + 1, col + 1)), cache and return.
  3. Call minPath(0, 0).

Example Walkthrough

1Base case: bottom row values are their own min path sums
0
0
_
1
_
_
2
_
_
_
3
4
1
8
3
1/7

Code

The time is now optimal, but the memo table uses O(n^2) space. Since each row only depends on the row directly below it, a single 1D array can replace the full table.

Approach 3: Bottom-Up DP (Optimal)

Intuition

Instead of recursing from the top down, build the answer from the bottom row upward. The minimum path sum from any cell in the bottom row is the cell's value itself. For any cell above, the minimum path sum is the cell's value plus the smaller of the two minimum path sums from the row directly below.

Going bottom-up means each row only needs the results of the row immediately below it, so a single 1D array of size n holds everything required.

Algorithm

  1. Initialize a DP array with the values from the bottom row of the triangle.
  2. Iterate from the second-to-last row up to row 0.
  3. For each cell (row, col) in the current row, set dp[col] = triangle[row][col] + min(dp[col], dp[col + 1]).
  4. After processing all rows, return dp[0].

Example Walkthrough

1Initialize dp with bottom row: [4, 1, 8, 3]
0
4
1
1
2
8
3
3
1/8

Code